Pythonで配列を補完するための最小限の動きを見つけるプログラム

別の値の制限である偶数の長さの配列numがあるとします。 1回の移動で、numsの任意の値を1からlimitまでの別の値に置き換えることができます。すべてのインデックスiについて、nums [i] + nums [n-1-i]が同じ数に等しい場合、配列は相補的であると言われます。したがって、numsを補完するために必要な最小移動数を見つける必要があります。

したがって、入力がnums =[1,4,2,3] limit =4のような場合、出力は1になります。これは、1回の移動でインデックス1から2の要素を作成できるため、配列は[1,2 、2,3]、次にnums [0] + nums [3] =4、nums [1] + nums [2] =4、nums [2] + nums [1] =4、nums [3] + nums [ 0] =4

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

• n：=numsのサイズ
• mid：=n/2の商
• zero_moves：=整数型の値の空のマップ
• start：=サイズの配列（2*制限+1）、0で埋める
• end：=サイズの配列（2*制限+1）、0で埋める
• res：=無限大
• 0からmid-1の範囲のiの場合、do
  • x：=nums [i]
  • y：=nums [n --1 --i]
  • zero_moves [x + y]：=zero_moves [x + y] + 1
  • start [1 +最小のx、y]を1増やします
  • end [limit + maximum of x、y]を1増やします
• 間隔：=0
• 範囲2から制限*2のターゲットについては、
  • 間隔：=間隔+開始[ターゲット]
  • コスト：=2 *（中間-間隔）+間隔-zero_moves[ターゲット]
  • res：=最小のresとコスト
  • 間隔：=間隔-end [target]
• return res

例

理解を深めるために、次の実装を見てみましょう-

from collections import defaultdict
def solve(nums, limit):
   n = len(nums)
   mid = n // 2

   zero_moves = defaultdict(int)

   start = [0] * (2 * limit + 1)
   end = [0] * (2 * limit + 1)
   res = float('inf')
   for i in range(mid):
      x = nums[i]
      y = nums[n - 1 - i]
      zero_moves[x + y] += 1
      start[min(x, y) + 1] += 1
      end[max(x, y) + limit] += 1

   intervals = 0
   for target in range(2, limit * 2 + 1):
      intervals += start[target]
      cost = 2 * (mid - intervals) + intervals - zero_moves[target]
      res = min(res, cost)
      intervals -= end[target]
   return res

nums = [1,4,2,3]
limit = 4
print(solve(nums, limit))

入力

[1,4,2,3], 4

出力

1