Chương trình giảm thiểu độ lệch trong mảng trong Python

Giả sử chúng ta có một số mảng. Chúng ta có thể thực hiện hai loại phép toán trên bất kỳ phần tử nào của mảng với số lần bất kỳ

• Đối với các phần tử chẵn, hãy chia nó cho 2

• Đối với các phần tử lẻ, hãy nhân nó với 2.

Bây giờ độ lệch của mảng là sự khác biệt lớn nhất giữa hai phần tử bất kỳ trong mảng. Chúng ta phải tìm độ lệch tối thiểu mà mảng có thể có sau khi thực hiện một số thao tác. Vì vậy, nếu đầu vào là nums =[6,3,7,22,5], thì đầu ra sẽ là 5 vì chúng ta có thể tạo ourarray trong một hoạt động [6,6,7,22,5] và trong hoạt động thứ hai [6,6,7,22,10] và trong hoạt động không anh hùng [6,6,7,11,10], bây giờ độ lệch là 11- 6 =5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp số lượng danh sách

• max_v:=phần tử tối đa của nums

• min_v:=phần tử tối thiểu của nums

• đống số lượng

• res:=max_v - min_v

• trong khi nums [0] là số lẻ, hãy làm theo

  • v:=phần tử bật lên từ số hàng đợi đống

  • v:=2 * v

  • chèn v vào số hàng đợi heap

  • min_v:=nums [0]

  • max_v:=tối đa v và max_v

  • res:=tối thiểu của res và (max_v - min_v)

• nums:=danh sách tất cả các số trong n và theo thứ tự âm

• heapify số hàng đợi heap

• trong khi nums [0] là số chẵn, do

  • v:=- (phần tử được bật lên từ số hàng đợi đống)

  • v:=thương số của (v / 2)

  • chèn -v vào số hàng đợi heap

  • max_v:=-nums [0]

  • min_v:=tối thiểu là min_v và v

  • res:=tối thiểu của res và (max_v - min_v)

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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))

Đầu vào

[6,3,7,22,5]

Đầu ra

5