用 Python 编写程序，查找 K 个连续数的最小相邻交换

pythonserver side programmingprogramming更新于 2025/12/7 23:40:17

假设我们有一个二进制数组 nums 和一个值 k。我们可以在一次移动中，选择两个相邻的索引并交换它们的值。我们必须找到所需的最少移动次数，以使 nums 具有 k 个连续的 1。

因此，如果输入为 nums = [1,0,0,1,0,1,0,1]，k = 3，则输出将为 2，因为在一次交换中，我们可以将数组从 [1,0,0,1,0,1,0,1] 变为 [1,0,0,0,1,1,0,1]，然后是 [1,0,0,0,1,1,1,0]。

为了解决这个问题，我们将遵循以下步骤 −

j := 0
val := 0
ans := 999999
loc := a new列表
对于每个索引 i 和 nums 中的值 x，执行
- 如果 x 非零，则
  - 将 i 插入到 loc 的末尾
  - m := (j + loc 的大小 - 1) /2 的商
  - val := val + loc[-1] - loc[m] - (loc 的大小 -j)/2 的商
  - 如果 loc 的长度 - j > k，则
    - m := (j + loc 的大小) /2 的商
    - val := val - loc[m] - loc[j] - (loc -j 的大小)/2 的商
    - j := j + 1
  - 如果 loc -j 的大小与 k 相同，则
    - ans := ans 和 val 的最小值
返回 ans

示例

让我们看看下面的实现以便更好地理解

def solve(nums, k):
   j = val = 0
   ans = 999999
   loc = []
   for i, x in enumerate(nums):
      if x:
         loc.append(i)
         m = (j + len(loc) - 1)//2
         val += loc[-1] - loc[m] - (len(loc)-j)//2
         if len(loc) - j > k:
            m = (j + len(loc))//2
            val -= loc[m] - loc[j] - (len(loc)-j)//2
            j += 1
         if len(loc)-j == k:
            ans = min(ans, val)
   return ans

nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))