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

看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級別的第270題（順位題號是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個芯片位于位置chips[i]。

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

• 將第i個芯片向左或向右移動2個單位，成本為0。
• 將第i個芯片向左或向右移動1個單位，成本為1。

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

例如：

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

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

限制條件：

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

第一種解法

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

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

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

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

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

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

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

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

小結(jié)

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

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