โปรแกรมเพื่อลดค่าเบี่ยงเบนในอาร์เรย์ใน Python

สมมติว่าเรามีตัวเลขอาร์เรย์ เราสามารถดำเนินการสองประเภทกับองค์ประกอบใด ๆ ของอาร์เรย์กี่ครั้งก็ได้

• สำหรับองค์ประกอบที่เท่ากัน ให้หารด้วย 2

• สำหรับองค์ประกอบคี่ ให้คูณด้วย 2

ตอนนี้ค่าเบี่ยงเบนของอาร์เรย์คือความแตกต่างสูงสุดระหว่างสององค์ประกอบในอาร์เรย์ เราต้องหาค่าเบี่ยงเบนขั้นต่ำที่อาร์เรย์สามารถมีได้หลังจากดำเนินการจำนวนหนึ่ง ดังนั้นหากอินพุตมีค่าเท่ากับ nums =[6,3,7,22,5] ผลลัพธ์จะเป็น 5 เพราะเราสามารถสร้างอาร์เรย์ของเราได้ หนึ่งการดำเนินการ [6,6,7,22,5] และในการดำเนินการที่สอง [6,6,7,22,10] และในการดำเนินการอื่น [6,6,7,11,10] ตอนนี้ค่าเบี่ยงเบนคือ 11- 6 =5.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เรียงเลขรายการ

• max_v :=องค์ประกอบสูงสุดของ nums

• min_v :=องค์ประกอบขั้นต่ำของ nums

• heapify nums

• res :=max_v - min_v

• ในขณะที่ nums[0] เป็นเลขคี่ ทำ

  • v :=องค์ประกอบป๊อปจากหมายเลขคิวฮีป

  • วี :=2 * วี

  • แทรก v ลงในหมายเลขคิวฮีป

  • min_v :=nums[0]

  • max_v :=สูงสุดของ v และ max_v

  • res :=ขั้นต่ำของ res และ (max_v - min_v)

• nums :=รายการของตัวเลขทั้งหมดใน n และในลำดับติดลบ

• heapify หมายเลขคิวฮีป

• ในขณะที่ nums[0] เป็นคู่ ทำ

  • v :=- (องค์ประกอบปรากฏขึ้นจากหมายเลขคิวฮีป)

  • v :=ผลหารของ (v/2)

  • แทรก -v ลงในหมายเลขคิวฮีป

  • max_v :=-nums[0]

  • min_v :=ขั้นต่ำของ min_v และ v

  • res :=ขั้นต่ำของ res และ (max_v - min_v)

• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

import heapq
def solve(nums):
   nums.sort()
   max_v,min_v = nums[-1],nums[0]
   heapq.heapify(nums)
   res = max_v-min_v
   while nums[0]%2==1:
      v = heapq.heappop(nums)
      v = 2 * v
      heapq.heappush(nums, v)
      min_v = nums[0]
      max_v = max(v, max_v)
      res = min(res, max_v - min_v)

   nums = [-n for n in nums]
   heapq.heapify(nums)
   while nums[0]%2==0:
      v = -heapq.heappop(nums)
      v = v // 2
      heapq.heappush(nums, -v)
      max_v = -nums[0]
      min_v = min(min_v,v)
      res = min(res, max_v - min_v)

   return res

nums = [6,3,7,22,5]
print(solve(nums))

อินพุต

[6,3,7,22,5]

ผลลัพธ์

5