Pythonで配列の偏差を最小限に抑えるプログラム

配列numsがあるとします。配列の任意の要素に対して、2種類の操作を何度でも実行できます

• 偶数要素の場合は、2で割ります

• 奇数の要素の場合は、2を掛けます。

これで、配列の偏差は、配列内の任意の2つの要素間の最大差になります。いくつかの操作を実行した後、配列が持つことができる最小の偏差を見つける必要があります。したがって、入力がnums =[6,3,7,22,5]の場合、配列を次のように作成できるため、出力は5になります。 1つの操作[6,6,7,22,5]と2番目の操作[6,6,7,22,10]、および別の操作[6,6,7,11,10]では、偏差は11-になります。 6=5。

これを解決するには、次の手順に従います-

• リスト番号を並べ替える

• max_v：=numsの最大要素

• min_v：=numsの最小要素

• numsをヒープ化する

• res：=max_v --min_v

• nums [0]は奇数ですが、実行してください

  • v：=ヒープキュー番号からポップされた要素

  • v：=2 * v

  • vをヒープキュー番号に挿入します

  • min_v：=nums [0]

  • max_v：=vとmax_vの最大値

  • res：=最小のresおよび（max_v --min_v）

• nums：=nおよび負の順序のすべての数値のリスト

• ヒープキューの数をヒープ化する

• 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