專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

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

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

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

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

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

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

給你一個(gè)整數(shù) n，即數(shù)組的長(zhǎng)度。請(qǐng)你返回使數(shù)組 arr 中所有元素相等所需的 最小操作數(shù) 。

示例1：

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

示例2：

輸入：n = 6 輸出：9

• 1 <= n <= 10^4

問題分析

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

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

如果 n 是偶數(shù)，比如是 6 ，那么數(shù)組就是[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 是奇數(shù)還是偶數(shù)，只需要數(shù)組前面一半的值都累加到 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)化一下，對(duì)于需要累加的數(shù)字個(gè)數(shù)是n/2，每個(gè)數(shù)字累加的結(jié)果都是 n ，所以最終累加的數(shù)字之和是 n*n/2，而累加之前的數(shù)字之和是(n/2)^2，兩者相減為 n*n/4，所以我們通過公式只需要一步即可得到結(jié)果。

JAVA：

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

C++：

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

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。