【算法思考记录】力扣2134. 最少交换次数来组合所有的 1 II【C++,滑动窗口】

本文介绍: 本题目要求我们找到在一个环形二进制数组中，通过最少的交换次数把所有的 1 聚集在一起的方法。数组的环形特性意味着第一个元素和最后一个元素是相邻的。我们需要考虑数组的这种特殊结构来找到最优解。

最少 交换 次数来组合所有的 1 II – 解题 思路与代码 分析

题目 描述

本题目要求我们找到在一个环形二进制数组中，通过最少的交换次数把所有的 1 聚集在一起的方法。数组的环形特性意味着第一个元素和最后一个元素是相邻的。我们需要考虑数组的这种特殊结构来找到最优解。

示例 分析

示例 1：nums = [0,1,0,1,1,0,0]。最少需要交换 1 次。
示例 2：nums = [0,1,1,1,0,0,1,1,0]。最少需要交换 2 次。
示例 3：nums = [1,1,0,0,1]。由于环形特性，所有 1 已经聚集在一起，因此不需要交换。

解题思路

解决这个问题的核心思想是使用滑动窗口技术。首先统计数组中 1 的数量，这将决定我们滑动窗口的大小。然后我们遍历整个数组两次（考虑到环形结构），统计窗口内 0 的数量，这个数量就是需要交换的次数。我们寻找最小的这个交换次数作为答案。

答案 代码 分析

class Solution {
public:
    int minSwaps(vector&lt;int&gt;&amp; nums) {
        int n = nums.size();
        int win_size = count(nums.begin(), nums.end(), 1);
        if (win_size == 0) {
            return 0;
        }

        int round_cnt = 0;
        int first_win_ridx = win_size - 1;
        int ans = 1e5; // 初始化一个大数作为初始答案
        int left = 0, right = 0;
        int win_zero_num = 0;
        int win_ele_num = 1;

        while (round_cnt < 2) {
            if (nums[right] == 0) {
                win_zero_num++;
            }

            if (win_ele_num == win_size) {
                ans = min(ans, win_zero_num);
                if (nums[left] == 0) {
                    win_zero_num--;
                }
                left++;
                left %= n; // 考虑环形数组特性
                win_ele_num--;
            }

            right++;
            right %= n; // 考虑环形数组特性
            if (right == first_win_ridx) {
                round_cnt++;
            }

            win_ele_num++;
        }
        return ans;
    }
};