在 Python 中找到 K 个连续交换的最小相邻交换的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个二进制数组 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] .

示例

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

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))

输入

[1,0,0,1,0,1,0,1], 3

2

以上是 在 Python 中找到 K 个连续交换的最小相邻交换的程序 的全部内容， 来源链接： utcz.com/z/360139.html