class Solution {
public:
int minSwaps(vector<int>& nums) {
}
};
2134. 最少交换次数来组合所有的 1 II
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
示例 1：
输入：nums = [0,1,0,1,1,0,0] 输出：1 解释：这里列出一些能够将所有 1 聚集在一起的方案： [0,0,1,1,1,0,0] 交换 1 次。 [0,1,1,1,0,0,0] 交换 1 次。 [1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。 无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。 因此，需要的最少交换次数为 1 。
示例 2：
输入：nums = [0,1,1,1,0,0,1,1,0] 输出：2 解释：这里列出一些能够将所有 1 聚集在一起的方案： [1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。 [1,1,1,1,1,0,0,0,0] 交换 2 次。 无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。 因此，需要的最少交换次数为 2 。
示例 3：
输入：nums = [1,1,0,0,1] 输出：0 解释：得益于数组的环形特性，所有的 1 已经聚集在一起。 因此，需要的最少交换次数为 0 。
提示：
1 <= nums.length <= 105nums[i] 为 0 或者 1原站题解
python3 解法, 执行用时: 248 ms, 内存消耗: 19.8 MB, 提交时间: 2023-06-20 14:58:41
class Solution:
def minSwaps(self, nums: List[int]) -> int:
n = len(nums)
cnt = sum(nums)
if cnt == 0:
return 0
cur = 0
for i in range(cnt):
cur += (1 - nums[i])
ans = cur
for i in range(1, n):
if nums[i - 1] == 0:
cur -= 1
if nums[(i + cnt - 1) % n] == 0:
cur += 1
ans = min(ans, cur)
return ans
cpp 解法, 执行用时: 80 ms, 内存消耗: 78.5 MB, 提交时间: 2023-06-20 14:58:01
class Solution {
public:
int minSwaps(vector<int>& nums) {
int n = nums.size();
int cnt = accumulate(nums.begin(), nums.end(), 0); // 0 的个数
if (cnt == 0) {
return 0;
}
int cur = 0;
for (int i = 0; i < cnt; ++i) {
cur += (1 - nums[i]);
}
int ans = cur;
for (int i = 1; i < n; ++i) {
if (nums[i - 1] == 0) {
--cur;
}
if (nums[(i + cnt - 1) % n] == 0) {
++cur;
}
ans = min(ans, cur);
}
return ans;
}
};
java 解法, 执行用时: 14 ms, 内存消耗: 54.7 MB, 提交时间: 2023-06-20 14:56:51
class Solution {
public int minSwaps(int[] nums) {
int n = nums.length;
int ans = n, oneCnt = 0;
// 统计数组中 1 的数量
for (int num : nums) {
if (num == 1) oneCnt++;
}
// 开一个宽度为 oneCnt 的窗口， 统计窗口里面 0 的数量 zeroCnt
// 最少的 zeroCnt 即为此题答案
for (int i = 0, zeroCnt = 0; i < 2 * n; i++) {
if (i >= oneCnt) {
ans = Math.min(ans, zeroCnt);
// 右移窗口时，被移除的数字是 0 则 zeroCnt--
if (nums[(i - oneCnt) % n] == 0) {
zeroCnt--;
}
}
if (nums[i % n] == 0) zeroCnt++;
}
return ans;
}
}
golang 解法, 执行用时: 84 ms, 内存消耗: 8.6 MB, 提交时间: 2023-06-20 14:55:29
// 断环成链 + 滑动窗口
func minSwaps(nums []int) int {
tot1 := 0
for _, num := range nums {
tot1 += num
}
cnt1, maxCnt1 := 0, 0
nums = append(nums, nums...) // 断环成链
for i, num := range nums {
cnt1 += num
if i >= tot1 { // 滑窗
cnt1 -= nums[i-tot1]
if cnt1 > maxCnt1 {
maxCnt1 = cnt1
}
}
}
return tot1 - maxCnt1
}
python3 解法, 执行用时: 160 ms, 内存消耗: 21.3 MB, 提交时间: 2023-06-20 14:54:39
# 滑动窗口
class Solution:
def minSwaps(self, nums: List[int]) -> int:
n, cnt, nums = len(nums), nums.count(1), nums * 2
ans = cnt_ = sum(nums[:cnt])
for i in range(n):
if nums[i] != nums[i + cnt]:
cnt_ += nums[i + cnt] - nums[i]
ans = max(ans, cnt_)
return cnt - ans