526互联

2023-09-30：用go语言，给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1， 每一次移动，你可以选择 相邻 两个数字并将它们交换。 请你返回使 nums 中包含 k

发布时间 2023-09-30 15:11:36作者: 福大大架构师每日一题

2023-09-30：用go语言，给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1，

每一次移动，你可以选择 相邻 两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

输入：nums = [1,0,0,1,0,1], k = 2。

输出：1。

来自左程云。

答案2023-09-30：

步骤描述：

1.定义一个函数 minMoves(nums []int, k int)，传入一个整数数组 nums 和一个整数 k。

2.如果 k 等于 1，直接返回 0。

3.获取数组 nums 的长度 n。

4.计算目标窗口中索引和的左半部分，即 (k - 1)/2 个索引的和，赋值给 leftAimIndiesSum。

5.计算目标窗口中索引和的右半部分，即 (k-1)*k/2 - leftAimIndiesSum，赋值给 rightAimIndiesSum。

6.初始化一个变量 ans，并将其赋值为最大整数。

7.初始化左边窗口的起始索引 l 为 0，中间位置索引 m 为 (k - 1)/2，右边窗口的结束索引 r 为 k - 1。

8.计算左边窗口需要的 1 的个数 leftNeedOnes 为 (k - 1)/2 + 1。

9.初始化左边窗口的起始索引 leftWindowL 为 0，左边窗口的 1 的个数 leftWindowOnes 为 0，左边窗口中索引和的总和 leftWindowOnesIndiesSum 为 0。

10.遍历数组 nums，i 从 0 到 m-1，进行如下操作：

10.1.如果 nums[i] 等于 1，将 leftWindowOnes 加一，leftWindowOnesIndiesSum 加上 i。

11.计算右边窗口需要的 1 的个数 rightNeedOnes 为 k - leftNeedOnes。

12.初始化右边窗口的结束索引 rightWindowR 为 m，右边窗口的 1 的个数 rightWindowOnes 为 nums[m]，右边窗口中索引和的总和 rightWindowOnesIndiesSum 为 0。

13.如果 nums[m] 等于 1，将 rightWindowOnesIndiesSum 赋值为 m。

14.对于 l、m、r 从初始状态开始，进行如下操作：

14.1.如果 nums[m] 等于 1，将 leftWindowOnes 加一，leftWindowOnesIndiesSum 加上 m，rightWindowOnes 减一，rightWindowOnesIndiesSum 减去 m。

14.2.当 leftWindowOnes 大于 leftNeedOnes 时，如果 nums[leftWindowL] 等于 1，则将 leftWindowOnes 减一，leftWindowOnesIndiesSum 减去 leftWindowL，左窗口的起始索引 leftWindowL 加一。

14.3.当 rightWindowOnes 小于 rightNeedOnes 且 rightWindowR+1 小于 n 时，如果 nums[rightWindowR+1] 等于 1，则将 rightWindowOnes 加一，rightWindowOnesIndiesSum 加上 rightWindowR+1，右窗口的结束索引 rightWindowR 加一。

14.4.如果左窗口的 1 的个数等于 leftNeedOnes，右窗口的 1 的个数等于 rightNeedOnes，说明找到了满足要求的窗口。将 ans 更新为 leftAimIndiesSum 减去 leftWindowOnesIndiesSum，再加上 rightWindowOnesIndiesSum 减去 rightAimIndiesSum 和 ans 中的较小值。

14.5.更新 leftAimIndiesSum 为 m+1-l，更新 rightAimIndiesSum 为 r-m。

14.6.将 l 加一，m 加一，r 加一。

15.返回 ans。

总的时间复杂度：根据代码逐行分析，其中的遍历是线性时间复杂度 O(n)，其余操作的时间复杂度均为常数时间复杂度。所以总的时间复杂度为 O(n)。

总的额外空间复杂度：除了函数调用栈外，代码中没有使用额外空间，所以额外空间复杂度为 O(1)。

go完整代码如下：

package main

import (
	"fmt"
)

func minMoves(nums []int, k int) int {
	if k == 1 {
		return 0
	}
	n := len(nums)
	x := (k - 1) / 2
	leftAimIndiesSum := x * (x + 1) / 2
	rightAimIndiesSum := int((k-1)*k/2 - leftAimIndiesSum)
	ans := int(^uint(0) >> 1)
	l := 0
	m := (k - 1) / 2
	r := k - 1
	leftNeedOnes := m + 1
	leftWindowL := 0
	leftWindowOnes := 0
	leftWindowOnesIndiesSum := 0
	for i := 0; i < m; i++ {
		if nums[i] == 1 {
			leftWindowOnes++
			leftWindowOnesIndiesSum += i
		}
	}
	rightNeedOnes := k - leftNeedOnes
	rightWindowR := m
	rightWindowOnes := nums[m]
	rightWindowOnesIndiesSum := 0
	if nums[m] == 1 {
		rightWindowOnesIndiesSum = m
	}
	for ; r < n; l, m, r = l+1, m+1, r+1 {
		if nums[m] == 1 {
			leftWindowOnes++
			leftWindowOnesIndiesSum += m
			rightWindowOnes--
			rightWindowOnesIndiesSum -= m
		}
		for leftWindowOnes > leftNeedOnes {
			if nums[leftWindowL] == 1 {
				leftWindowOnes--
				leftWindowOnesIndiesSum -= leftWindowL
			}
			leftWindowL++
		}
		for rightWindowOnes < rightNeedOnes && rightWindowR+1 < n {
			if nums[rightWindowR+1] == 1 {
				rightWindowOnes++
				rightWindowOnesIndiesSum += rightWindowR + 1
			}
			rightWindowR++
		}
		if leftWindowOnes == leftNeedOnes && rightWindowOnes == rightNeedOnes {
			ans = min(ans, leftAimIndiesSum-leftWindowOnesIndiesSum+rightWindowOnesIndiesSum-rightAimIndiesSum)
		}
		leftAimIndiesSum += m + 1 - l
		rightAimIndiesSum += r - m
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	nums := []int{1, 0, 0, 1, 0, 1}
	k := 2
	result := minMoves(nums, k)
	fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下：

fn min_moves(nums: Vec<i32>, k: i32) -> i32 {
    if k == 1 {
        return 0;
    }
    let n = nums.len() as i32;
    let x = (k - 1) / 2;
    let mut left_aim_indices_sum = x * (x + 1) / 2;
    let mut right_aim_indices_sum = (k - 1) * k / 2 - left_aim_indices_sum;
    let mut ans = std::i32::MAX;
    let (mut l, mut m, mut r) = (0, (k - 1) / 2, k - 1);
    let left_need_ones = m + 1;
    let (mut left_window_l, mut left_window_ones, mut left_window_ones_indices_sum) = (0, 0, 0);

    for i in 0..m {
        if nums[i as usize] == 1 {
            left_window_ones += 1;
            left_window_ones_indices_sum += i as i32;
        }
    }

    let right_need_ones = k - left_need_ones;
    let (mut right_window_r, mut right_window_ones, mut right_window_ones_indices_sum) = (
        m,
        nums[m as usize],
        if nums[m as usize] == 1 { m as i32 } else { 0 },
    );

    while r < n {
        if nums[m as usize] == 1 {
            left_window_ones += 1;
            left_window_ones_indices_sum += m as i32;
            right_window_ones -= 1;
            right_window_ones_indices_sum -= m as i32;
        }

        while left_window_ones > left_need_ones {
            if nums[left_window_l] == 1 {
                left_window_ones -= 1;
                left_window_ones_indices_sum -= left_window_l as i32;
            }
            left_window_l += 1;
        }

        while right_window_ones < right_need_ones && right_window_r + 1 < n {
            if nums[(right_window_r + 1) as usize] == 1 {
                right_window_ones += 1;
                right_window_ones_indices_sum += (right_window_r + 1) as i32;
            }
            right_window_r += 1;
        }

        if left_window_ones == left_need_ones && right_window_ones == right_need_ones {
            ans = ans.min(
                left_aim_indices_sum - left_window_ones_indices_sum + right_window_ones_indices_sum
                    - right_aim_indices_sum,
            );
        }

        left_aim_indices_sum += (m + 1 - l) as i32;
        right_aim_indices_sum += (r - m) as i32;

        l += 1;
        m += 1;
        r += 1;
    }

    ans
}

fn main() {
    let nums = vec![1, 0, 0, 1, 0, 1];
    let k = 2;
    let result = min_moves(nums, k);
    println!("{}", result);
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

int minMoves(vector<int>& nums, int k) {
    if (k == 1) {
        return 0;
    }
    int n = nums.size();
    int x = (k - 1) / 2;
    int leftAimIndiesSum = x * (x + 1) / 2;
    int rightAimIndiesSum = (k - 1) * k / 2 - leftAimIndiesSum;
    int ans = INT_MAX;
    int l = 0;
    int m = (k - 1) / 2;
    int r = k - 1;
    int leftNeedOnes = m + 1;
    int leftWindowL = 0;
    int leftWindowOnes = 0;
    int leftWindowOnesIndiesSum = 0;
    for (int i = 0; i < m; i++) {
        if (nums[i] == 1) {
            leftWindowOnes++;
            leftWindowOnesIndiesSum += i;
        }
    }
    int rightNeedOnes = k - leftNeedOnes;
    int rightWindowR = m;
    int rightWindowOnes = nums[m];
    int rightWindowOnesIndiesSum = nums[m] == 1 ? m : 0;
    for (; r < n; l++, m++, r++) {
        if (nums[m] == 1) {
            leftWindowOnes++;
            leftWindowOnesIndiesSum += m;
            rightWindowOnes--;
            rightWindowOnesIndiesSum -= m;
        }
        while (leftWindowOnes > leftNeedOnes) {
            if (nums[leftWindowL] == 1) {
                leftWindowOnes--;
                leftWindowOnesIndiesSum -= leftWindowL;
            }
            leftWindowL++;
        }
        while (rightWindowOnes < rightNeedOnes && rightWindowR + 1 < n) {
            if (nums[rightWindowR + 1] == 1) {
                rightWindowOnes++;
                rightWindowOnesIndiesSum += rightWindowR + 1;
            }
            rightWindowR++;
        }
        if (leftWindowOnes == leftNeedOnes && rightWindowOnes == rightNeedOnes) {
            ans = min(ans,
                leftAimIndiesSum - leftWindowOnesIndiesSum + rightWindowOnesIndiesSum - rightAimIndiesSum);
        }
        leftAimIndiesSum += m + 1 - l;
        rightAimIndiesSum += r - m;
    }
    return ans;
}

int main() {
    vector<int> nums = { 1, 0, 0, 1, 0, 1 };
    int k = 2;
    int result = minMoves(nums, k);
    cout << result << endl;
    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>

int minMoves(int* nums, int numsSize, int k) {
    if (k == 1) {
        return 0;
    }
    int x = (k - 1) / 2;
    int leftAimIndiesSum = x * (x + 1) / 2;
    int rightAimIndiesSum = ((k - 1) * k / 2 - leftAimIndiesSum);
    int ans = INT_MAX;
    int l = 0;
    int m = (k - 1) / 2;
    int r = k - 1;
    int leftNeedOnes = m + 1;
    int leftWindowL = 0;
    int leftWindowOnes = 0;
    int leftWindowOnesIndiesSum = 0;
    for (int i = 0; i < m; i++) {
        if (nums[i] == 1) {
            leftWindowOnes++;
            leftWindowOnesIndiesSum += i;
        }
    }
    int rightNeedOnes = k - leftNeedOnes;
    int rightWindowR = m;
    int rightWindowOnes = nums[m];
    int rightWindowOnesIndiesSum = nums[m] == 1 ? m : 0;
    for (; r < numsSize; l++, m++, r++) {
        if (nums[m] == 1) {
            leftWindowOnes++;
            leftWindowOnesIndiesSum += m;
            rightWindowOnes--;
            rightWindowOnesIndiesSum -= m;
        }
        while (leftWindowOnes > leftNeedOnes) {
            if (nums[leftWindowL] == 1) {
                leftWindowOnes--;
                leftWindowOnesIndiesSum -= leftWindowL;
            }
            leftWindowL++;
        }
        while (rightWindowOnes < rightNeedOnes && rightWindowR + 1 < numsSize) {
            if (nums[rightWindowR + 1] == 1) {
                rightWindowOnes++;
                rightWindowOnesIndiesSum += rightWindowR + 1;
            }
            rightWindowR++;
        }
        if (leftWindowOnes == leftNeedOnes && rightWindowOnes == rightNeedOnes) {
            ans = min(ans, leftAimIndiesSum - leftWindowOnesIndiesSum + rightWindowOnesIndiesSum - rightAimIndiesSum);
        }
        leftAimIndiesSum += m + 1 - l;
        rightAimIndiesSum += r - m;
    }
    return ans;
}

int main() {
    int nums[] = { 1, 0, 0, 1, 0, 1 };
    int k = 2;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = minMoves(nums, numsSize, k);
    printf("%d\n", result);
    return 0;
}

在这里插入图片描述