1217-玩筹码

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

有 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

方法一：贪心

思路与算法

首先很容易得出：

  1. 从某一个偶（奇）数位置 p_i 改变到另一个偶（奇）数位置 p_j，不妨设 p_i < p_j，那么一定 \exists k \in \mathbb{N}^* 使得 p_i + 2k = p_j 成立，即此时的最小开销为 0。
  2. 从某一个偶（奇）数位置 p_i 改变到另一个奇（偶）数位置 p_j，不妨设 p_i < p_j，那么一定 \exists k \in \mathbb{N 使得 p_i + 2k + 1 = p_j 成立，即此时的最小开销为 1。

那么我们可以把初始每一个偶数位置的「筹码」看作一个整体，每一个奇数位置的「筹码」看作一个整体。因为我们的目标是最后将全部的「筹码」移动到同一个位置，那么最后的位置只有两种情况：

  1. 移动到某一个偶数位置，此时的开销最小值就是初始奇数位置「筹码」的数量。
  2. 移动到某一个奇数位置，此时的开销最小值就是初始偶数位置「筹码」的数量。

那么这两种情况中的最小值就是最后将所有筹码移动到同一位置上所需要的最小代价。

代码

[sol1-Python3]
1
2
3
4
class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        cnt = Counter(p % 2 for p in position)  # 根据模 2 后的余数来统计奇偶个数
        return min(cnt[0], cnt[1])
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int even = 0, odd = 0;
        for (int pos : position) {
            if (pos % 2) {
                odd++;
            } else {
                even++;
            }
        }
        return min(odd, even);
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minCostToMoveChips(int[] position) {
        int even = 0, odd = 0;
        for (int pos : position) {
            if ((pos & 1) != 0) {
                odd++;
            } else {
                even++;
            }
        }
        return Math.min(odd, even);
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int MinCostToMoveChips(int[] position) {
        int even = 0, odd = 0;
        foreach (int pos in position) {
            if ((pos & 1) != 0) {
                odd++;
            } else {
                even++;
            }
        }
        return Math.Min(odd, even);
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int minCostToMoveChips(int* position, int positionSize){
    int even = 0, odd = 0;
    for (int i = 0; i < positionSize; i++) {
        if (position[i] & 1) {
            odd++;
        } else {
            even++;
        }
    }
    return MIN(odd, even);
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var minCostToMoveChips = function(position) {
    let even = 0, odd = 0;
    for (const pos of position) {
        if ((pos & 1) !== 0) {
            odd++;
        } else {
            even++;
        }
    }
    return Math.min(odd, even);
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func minCostToMoveChips(position []int) int {
    cnt := [2]int{}
    for _, p := range position {
        cnt[p%2]++
    }
    return min(cnt[0], cnt[1])
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 position 的长度，只对数组进行了一次遍历。

  • 空间复杂度：O(1)，仅使用常数变量。

 Comments
On this page
1217-玩筹码