LeetCode - 2134 最少交换次数来组合所有的 1 II

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

题目来源

2134. 最少交换次数来组合所有的 1 II - 力扣（LeetCode）

题目描述

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

示例

提示

• 1 <= nums.length <= 105
• nums[i] 为 0 或者 1

题目解析

本题和算法 - 最少交换次数来组合所有的1_伏城之外的博客-CSDN博客

算法 - 最少交换次数_伏城之外的博客-CSDN博客

题目的区别，在于本题是环形数组，上面两个题目的数组不是环形的。

但是环形数组并不意味着难度更大，只是单纯地扩展了组合的情况而已，如下图所示 

 因此，只要在前面算法题的解题思路上，扩展一些情况即可

算法源码

function getMinSwapCount(arr) {
	// 统计1的个数
	let count = arr.reduce((pre, cur) => cur === 1 ? pre + 1 : pre, 0)
	
	if(count === 1) return 0
	
	let minSwapCount = 0
	for(let i=0; i<count; i++) {
		if(arr[i] === 0) minSwapCount++
	}
	
	let len = arr.length
	let tmpSwapCount = minSwapCount
	for(let i=1; i<len; i++){
		let preLeft = i-1
		let right = i + count - 1
		
        // 滑窗有边界可以越界，越界后索引相当于从头来，比如right=arr.length索引等价于right=0
		if(right >= len) {
			right -= len
		}
		
		if(arr[right]===1 && arr[preLeft]===0) {
			tmpSwapCount--
		} else if(arr[right]===0 && arr[preLeft]===1) {
			tmpSwapCount++
		}
		minSwapCount = Math.min(minSwapCount, tmpSwapCount)
	}
	
	return minSwapCount
}

console.log(getMinSwapCount([0,1,0,1,1,0,0]))
console.log(getMinSwapCount([0,1,1,1,0,0,1,1,0]))
console.log(getMinSwapCount([1,1,0,0,1]))