1217.md

title	description	keywords
1217. 玩筹码	LeetCode 1217. 玩筹码题解，Minimum Cost to Move Chips to The Same Position，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1217. 玩筹码 玩筹码 Minimum Cost to Move Chips to The Same Position 解题思路 贪心 数组 数学

1217. 玩筹码

🟢 Easy  🔖  贪心 数组 数学  🔗 力扣 LeetCode

题目

We have n chips, where the position of the ith chip is position[i].

We need to move all the chips to the same position. In one step, we can change the position of the ith chip from position[i] to:

• position[i] + 2 or position[i] - 2 with cost = 0.
• position[i] + 1 or position[i] - 1 with cost = 1.

Return the minimum cost needed to move all the chips to the same position.

Example 1:

Input: position = [1,2,3]

Output: 1

Explanation: First step: Move the chip at position 3 to position 1 with cost = 0.

Second step: Move the chip at position 2 to position 1 with cost = 1.

Total cost is 1.

Example 2:

Input: position = [2,2,2,3,3]

Output: 2

Explanation: We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost = 2.

Example 3:

Input: position = [1,1000000000]

Output: 1

Constraints:

• 1 <= position.length <= 100
• 1 <= position[i] <= 10^9

题目大意

有 n 个筹码。第 i 个筹码的位置是 position[i] 。

我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:

• position[i] + 2 或 position[i] - 2 ，此时 cost = 0
• position[i] + 1 或 position[i] - 1 ，此时 cost = 1

返回将所有筹码移动到同一位置上所需要的 最小代价 。

示例 1：

输入： position = [1,2,3]

输出： 1

解释： 第一步:将位置 3 的筹码移动到位置 1，成本为 0。

第二步:将位置 2 的筹码移动到位置 1，成本= 1。

总成本是 1。

示例 2：

输入： position = [2,2,2,3,3]

输出： 2

解释： 我们可以把位置 3 的两个筹码移到位置 2。每一步的成本为 1。总成本= 2。

示例 3:

输入： position = [1,1000000000]

输出： 1

提示：

• 1 <= position.length <= 100
• 1 <= position[i] <= 10^9

解题思路

筹码移动到距离为 2 的位置代价为 0，因此我们可以自由移动筹码到 奇数位置 或 偶数位置。

为了代价最小，可以先将所有筹码聚集到相邻的奇数位置和偶数位置，然后将较少的一摞移动到较多的一摞上去。

1. 统计奇数位置和偶数位置的筹码个数。
2. 将奇数位置的筹码移到偶数位置（或者相反），代价为较小的一方的个数，因为这些筹码必须跨越 1 的距离。

复杂度分析

• 时间复杂度：O(n)，遍历数组统计奇数和偶数筹码个数。
• 空间复杂度：O(1)，仅使用常量空间存储变量 odd 和 even。

代码

/**
 * @param {number[]} position
 * @return {number}
 */
var minCostToMoveChips = function (position) {
	let odd = 0,
		even = 0; // 奇数位置和偶数位置的筹码数量

	for (let num of position) {
		if (num % 2 === 0) {
			even++; // 偶数位置筹码
		} else {
			odd++; // 奇数位置筹码
		}
	}

	// 返回移动代价最小的值
	return Math.min(even, odd);
};

相关题目

题号	标题	题解	标签	难度	力扣
1769	移动所有球到每个盒子所需的最小操作数	[✓]	数组 字符串 前缀和	🟠	🀄️ 🔗
2578	最小和分割		贪心 数学 排序	🟢	🀄️ 🔗