Python程式：查詢使陣列互補所需的最小移動次數

假設我們有一個偶數長度的陣列nums和另一個值limit。在一次移動中，我們可以將nums中的任何值替換為1到limit（含）之間的另一個值。如果對於所有索引i，nums[i] + nums[n-1-i]都等於同一個數字，則稱該陣列是互補的。因此，我們必須找到使nums互補所需的最小移動次數。

因此，如果輸入類似於nums = [1,4,2,3] limit = 4，則輸出將為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 * limit + 1)的陣列，並填充為0
  • end := 一個大小為(2 * limit + 1)的陣列，並填充為0
  • res := 無窮大
  • 對於範圍0到mid - 1的i，執行以下操作：
    • x := nums[i]
    • y := nums[n - 1 - i]
    • zero_moves[x + y] := zero_moves[x + y] + 1
    • 將start[1 + min(x, y)]增加1
    • 將end[limit + max(x, y)]增加1
  • intervals := 0
  • 對於範圍2到limit*2的target，執行以下操作：
    • intervals := intervals + start[target]
    • cost := 2 *(mid - intervals) + intervals - zero_moves[target]
    • res := res和cost的最小值
    • intervals := intervals - end[target]
  • 返回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

更新於： 2021年10月5日

273次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始
廣告