题目描述
数轴上放置了一些筹码,每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一(不限操作次数,0 次也可以):
-
将第 i 个筹码向左或者右移动 2 个单位,代价为 0。
-
将第 i 个筹码向左或者右移动 1 个单位,代价为 1。
-
最开始的时候,同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置(任意位置)上所需要的最小代价。
样例
输入:chips = [1,2,3]
输出:1
解释:第二个筹码移动到位置三的代价是 1,第一个筹码移动到位置三的代价是 0,总代价为 1。
输入:chips = [2,2,2,3,3]
输出:2
解释:第四和第五个筹码移动到位置二的代价都是 1,所以最小总代价为 2。
算法分析
1、由于移动两步的代价为0,所以优先进行此操作,把奇数的数和偶数的数分别串在同一个位置
2、并且将得到的两串数靠着一起,再把长度较短的全部串在长度较长的上,最少总代价为min(x, y)
时间复杂度 $O(n)$
Java 代码
class Solution {
public int minCostToMoveChips(int[] chips) {
int n = chips.length;
//计算出位置是奇数的筹码个数,计算出位置是偶数的筹码个数
int x = 0;
int y = 0;
for(int i = 0;i < n;i++)
{
if(chips[i] % 2 == 0) y++;
else x++;
}
return Math.min(x, y);
}
}