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 :=숫자의 최대 요소
min_v :=숫자의 최소 요소
많은 숫자
res :=max_v - min_v
nums[0]이 홀수인 동안 수행
- v :=힙 큐 번호에서 팝된 요소
- v :=2 * v
- 힙 큐 번호에 v 삽입
- min_v :=숫자[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]