最少交换次数来组合所有的 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<int>& 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;
}
};
- 初始化窗口大小为数组中 1 的数量。
- 通过双指针技术移动窗口,统计窗口中 0 的数量。
- 使用
round_cnt
确保遍历整个数组两次,因为数组是环形的。 - 当窗口移动时,更新所需的最少交换次数。