題目描述
這是 LeetCode 上的 1217. 玩籌碼 涂臣，難度為 簡單。
Tag : 「貪心」礁遵、「枚舉」
有 n 個籌碼兑燥。第 個籌碼的位置是
position[i]诚些。
我們需要把所有籌碼移到同一個位置。在一步中，我們可以將第 個籌碼的位置從
改變?yōu)?
-
position[i] + 2 或 position[i] - 2，此時cost = 0 -
position[i] + 1 或 position[i] - 1哑舒，此時cost = 1
返回將所有籌碼移動到同一位置上所需要的 最小代價(jià) 。
示例 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
提示：
貪心 + 枚舉目標(biāo)位置
假設(shè)移動的目標(biāo)位置是 钩蚊，當(dāng)前所在位置是
，將小球從
移動到
的成本取決于兩位置距離的「奇偶性」蹈矮，距離為偶數(shù)時成本固定為
砰逻，距離為奇數(shù)時成本固定為
。
同時我們可以通過「分情況討論」來證明泛鸟，所有小球移動到一個全新位置（起始沒有小球的位置）蝠咆，結(jié)果不會變好，假設(shè)所選擇的最終（全新）位置為 ：
- 假設(shè)選擇的位置
導(dǎo)致所有數(shù)到位置
刚操，同時可知所有數(shù)的位置奇偶性相同，此時選擇所有數(shù)中的任意一個的位置再芋，同樣可得總成本為
- 假設(shè)選擇的位置
鉴逞，同時可知所有數(shù)的位置奇偶性相同，此時選擇所有數(shù)中的任意一個的位置司训，可得總成本為
- 假設(shè)選擇的位置
豁遭，偶數(shù)結(jié)果為
叭喜，可知
，同時我們通過調(diào)整
蓖谢。此時總的成本為
綜上溉知，我們可以枚舉所有已有的位置為目標(biāo)位置陨瘩，并通過奇偶性統(tǒng)計(jì)其余位置到目標(biāo)位置的成本，在所有已有位置中取最小的總成本即是答案级乍。
代碼：
class Solution {
public int minCostToMoveChips(int[] ps) {
int n = ps.length, ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int a = ps[i], cur = 0;
for (int j = 0; j < n; j++) {
int b = ps[j];
cur += Math.abs(a - b) % 2;
}
ans = Math.min(ans, cur);
}
return ans;
}
}
- 時間復(fù)雜度：
- 空間復(fù)雜度：
貪心 + 統(tǒng)計(jì)奇偶性
更進(jìn)一步舌劳，我們可以發(fā)現(xiàn)要使得「總的移動成本最優(yōu)」的目標(biāo)位置有無數(shù)個，只要目標(biāo)位置的奇偶性不變玫荣，即可確鄙醯總成本不變。
因此我們可以省去枚舉具體位置的操作捅厂，轉(zhuǎn)而統(tǒng)計(jì)原有數(shù)的奇偶位置個數(shù)贯卦，假設(shè)偶數(shù)位置有 個，奇數(shù)位置有
個焙贷，最終目標(biāo)位置選為偶數(shù)的成本為
撵割，最終目標(biāo)位置選為奇數(shù)的成本為
，即兩者中的最小值即是答案辙芍。
代碼：
class Solution {
public int minCostToMoveChips(int[] ps) {
int n = ps.length, a = 0;
for (int i : ps) a += i % 2;
return Math.min(a, n - a);
}
}
- 時間復(fù)雜度：
- 空間復(fù)雜度：
最后
這是我們「刷穿 LeetCode」系列文章的第 No.1217 篇啡彬，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目沸手，部分是有鎖題外遇，我們將先把所有不帶鎖的題目刷完。
在這個系列文章里面契吉，除了講解解題思路以外跳仿，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板捐晶。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼菲语，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 。
在倉庫地址里惑灵，你可以看到系列文章的題解鏈接山上、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解英支。
本文由mdnice多平臺發(fā)布
