這是小川的第421次更新，第454篇原創(chuàng)

看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第270題（順位題號(hào)是1217）。There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

• Move the i-th chip by 2 units to the left or to the right with a cost of 0.
• Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

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

Example 1:

Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Example 2:

Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

Constraints:

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

中文翻譯

有一些芯片，第i個(gè)芯片位于位置chips[i]。

你可以在任何芯片上多次執(zhí)行以下兩種類型的任何一種移動(dòng)（也可能為零次）：

• 將第i個(gè)芯片向左或向右移動(dòng)2個(gè)單位，成本為0。
• 將第i個(gè)芯片向左或向右移動(dòng)1個(gè)單位，成本為1。

最初時(shí)，在同一位置可以有兩個(gè)或多個(gè)芯片。返回將所有芯片移至同一位置（任何位置）所需的最低成本。

例如：

輸入：chips = [1,2,3]
輸出：1
說明：第二個(gè)芯片將以成本1移至位置3。第一個(gè)芯片將以成本0移至位置3。總成本為1。

輸入：chips = [2,2,2,3,3]
輸出：2
說明：第四和第五芯片都將移動(dòng)到成本為1的位置2。最低總成本為2。

限制條件：

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

第一種解法

一開始看題目，看的我一臉懵逼，這是個(gè)神馬題目介紹？

開始認(rèn)為是移動(dòng)元素到固定的一個(gè)索引位置上，計(jì)算移動(dòng)的最小成本，給的例子倒也能解釋，但是在試了其他幾組數(shù)據(jù)后，比如數(shù)組{1,3,5}，結(jié)果是0，與我設(shè)想的結(jié)果1對(duì)不上，思路是錯(cuò)的，肯定是理解錯(cuò)了題目的意思。沒辦法，只能繼續(xù)理解題意和用隨機(jī)數(shù)組驗(yàn)證思路了。在明白題目究竟想要我們做啥后，只想來一句，我服了you！

回歸正題，我們一起來看看這個(gè)題目的真面目。如果將題目中positon字眼，換成value，你就會(huì)很快明白題目在講什么了。

給了一個(gè)數(shù)組，其中元素都是大于等于1的正整數(shù)，可以對(duì)數(shù)組中的任意元素進(jìn)行兩種操作：將元素值加2或減2，成本為0；將元素值加1或減1，成本為1。這兩種操作都可以進(jìn)行多次，現(xiàn)在要將數(shù)組中的元素值全部變?yōu)橐粋€(gè)值，請(qǐng)問最低的成本是多少？

結(jié)合題目中的第二個(gè)例子來看，[2,2,2,3,3]，有3個(gè)2，2個(gè)3，有兩種辦法，可以將這5個(gè)數(shù)統(tǒng)一，第一是3個(gè)2都變3，成本是3；第二個(gè)辦法是2個(gè)3都變?yōu)?，成本是2，所以最小成本是2，也就是將2個(gè)3變?yōu)?。再來一個(gè)，比如[1,3,5]，將3減去2變?yōu)?，成本為0，將5減兩次2，也變?yōu)?，成本為0，最后總成本是0。

所以，這個(gè)問題本質(zhì)上是計(jì)算數(shù)組中奇數(shù)和偶數(shù)的個(gè)數(shù)。

• 如果數(shù)組元素全部為偶數(shù)，全變成2，成本為0。
• 如果數(shù)組元素全部為奇數(shù)，全變成1，成本為0。
• 如果奇數(shù)元素個(gè)數(shù)大于偶數(shù)元素個(gè)數(shù)，將偶數(shù)元素加1全變?yōu)槠鏀?shù)，成本是偶數(shù)元素的個(gè)數(shù)。
• 如果奇數(shù)元素個(gè)數(shù)小于偶數(shù)元素個(gè)數(shù)，將奇數(shù)元素加1全變?yōu)榕紨?shù)，成本是奇數(shù)元素的個(gè)數(shù)。

public int minCostToMoveChips(int[] chips) {
    int even = 0, odd = 0;
    for (int chip : chips) {
        if (chip%2 == 0) {
            even++; //偶數(shù)元素個(gè)數(shù)
        } else {
            odd++; //奇數(shù)元素個(gè)數(shù)
        }
    }
    return odd > even ? even : odd;
}

小結(jié)

算法專題目前已更新LeetCode算法題文章276+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、在看就是對(duì)我最大的回報(bào)和支持！