文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
我们首先计算数组中长度为0的1的个数k
我们需要遍历长度为k的窗口,找到窗口中0的数量的最小值即为答案
需要注意的是数组是环形的,我们的窗口也应该是环形的
题解代码
impl Solution {pub fn min_swaps(nums: Vec<i32>) -> i32 {let mut k = 0;for num in &nums {k += num;}let mut cnt = 0;for i in 0..k as usize {if nums[i] == 0 {cnt += 1;}}let mut ans = cnt;for i in 1..nums.len() {if nums[i - 1] == 0 {cnt -= 1;}if nums[(i - 1 + k as usize) % nums.len()] == 0 {cnt += 1;}ans = ans.min(cnt);}ans as i32}
}
题目链接
https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/