專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在某職場社交平臺上，一網友發(fā)文稱：畢業(yè)多久拿到了年薪百萬？該網友是一位Java開發(fā)工程師，本科畢業(yè)8年，今年漲薪加年終獎加激勵，算下來一年達到了百萬。

他分享了自己的薪資成長軌跡：從2017年的月薪9k到2025年的月薪42k+高績效，實現(xiàn)了年薪百萬，8年時間，收入翻了近10倍！期間就跳過一次槽，不知道大家8年收入翻了多少倍？

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1551題：使數組中所有元素相等的最小操作數，難度是中等。

存在一個長度為 n 的數組 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。

一次操作中，你可以選出兩個下標，記作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 減去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最終的目標是使數組中的所有元素都相等 。題目測試用例將會保證 ：在執(zhí)行若干步操作后，數組中的所有元素最終可以全部相等。

給你一個整數 n，即數組的長度。請你返回使數組 arr 中所有元素相等所需的 最小操作數 。

示例1：

輸入：n = 3 輸出：2 解釋：arr = [1, 3, 5] 第一次操作選出 x = 2 和 y = 0，使數組變?yōu)?[2, 3, 4] 第二次操作繼續(xù)選出 x = 2 和 y = 0，數組將會變成 [3, 3, 3]

示例2：

輸入：n = 6 輸出：9

• 1 <= n <= 10^4

問題分析

這題說的是給定一個數組[1,3,5,7……]，每次選擇兩個元素，一個加 1 ，一個減 1 ，求最終數組中的所有元素全部相等的最小操作次數。

如果 n 是奇數，比如是 5 ，那么數組就是[1,3,5,7,9]，只需要 3 和 7 每次分別加 1 和 減 1 ，執(zhí)行 2 次，都變成 5 。然后 1 和 9 每次分別加 1 和減 1 ，執(zhí)行 4 次，都變成 5 ，總共執(zhí)行 6 次。

如果 n 是偶數，比如是 6 ，那么數組就是[1,3,5,7,9,11]，只需要 5 和 7 分別加 1 和 減 1 ，執(zhí)行 1 次，都變成 6 。然后 3 和 9 每次分別加 1 和減 1 ，執(zhí)行 3 次，都變成 6 ，最后是 1 和 11 執(zhí)行 5 次，都變成 6 ，總共執(zhí)行 9 次。

所以我們可以找到規(guī)律，無論 n 是奇數還是偶數，只需要數組前面一半的值都累加到 n 即是這題的答案。

JAVA：

public int minOperations(int n) {     int ans = 0;     for (int i = 0; i < n / 2; i++) {         int cur = i * 2 + 1;         ans += n - cur;     }     return ans; }

C++：

public:     int minOperations(int n) {         int ans = 0;         for (int i = 0; i < n / 2; i++) {             int cur = i * 2 + 1;             ans += n - cur;         }         return ans;     }

這題我們還可以再來優(yōu)化一下，對于需要累加的數字個數是n/2，每個數字累加的結果都是 n ，所以最終累加的數字之和是 n*n/2，而累加之前的數字之和是(n/2)^2，兩者相減為 n*n/4，所以我們通過公式只需要一步即可得到結果。

JAVA：

public int minOperations(int n) {     return n * n >> 2; }

C++：

public:     int minOperations(int n) {         return n * n >> 2;     }

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。