話題背景

最近有道題在廠內(nèi)熱度很高，這是一位來自10年的鵝廠程序員從工作中抽象出來的算法題，來考考大家：

題目是這樣的：給定多個(gè)已經(jīng)排序好的數(shù)組（從小到大），在每個(gè)數(shù)組中挑選一個(gè)數(shù)字，計(jì)算這些數(shù)字的方差。請找出方差最小的數(shù)字組合（可能有多個(gè)），并輸出方差。舉例：[1，3，4，6，7，100 ][28，50，70，102 ][14，76，98 ]

選擇的數(shù)字組合應(yīng)該是100，102，98。 方差是2.67，要求性能盡可能的高，避免暴力窮舉。

來看看鵝廠工程師們都怎么解這道題吧！

鵝廠工程師的看法

@jk-CDG基礎(chǔ)平臺負(fù)責(zé)人▼

PS：簡單yy了一個(gè)思路，沒有驗(yàn)證過，僅供參考方差最小的序列，就是需要所有數(shù)離平均值最小，同時(shí)，考慮到你這兒的序列都是有序了基本上，可以參考多個(gè)有序序列的合并排序思路一樣

評論回復(fù)：

@bin·IEG

這個(gè)移動(dòng)難度比較大，無法保證向較大的方向移動(dòng)方差的函數(shù)的單調(diào)性

@aaron·WXG

如果每次只更新移動(dòng)一個(gè)，且的移動(dòng)的是ptr_sX值中最小的值的指針，似乎是個(gè)好方法？ 但是我無法證明這個(gè)一定能選到最好的？

似乎不對，這是反例：

[[252, 638, 754, 848, 887],[318, 384, 533],[31, 81, 105, 123, 203, 213, 217, 298, 536, 562, 603, 605, 624, 651, 850, 855, 918, 921, 950, 951],[189, 474],[175, 348, 416, 419, 525, 743, 807, 986]]

@jk·CDG

這兒每次move不是當(dāng)前指針的最小值，而是每個(gè)指針的下一個(gè)值的最小值，這樣能保證移動(dòng)后的平均值影響最小

這個(gè)case看起來是ok的

@zhenle-IEG開發(fā)工程師▼

假如:

• 數(shù)組的數(shù)量為M
• 數(shù)組里面的元素平均個(gè)數(shù)為N
• 數(shù)組里面所有元素的范圍為H

兩種方式： 

第一種：

• 遍歷第一個(gè)數(shù)組的每個(gè)元素，對于每個(gè)元素通過二分去剩下數(shù)組里面找到最接近的元素。
• 還需要對于每個(gè)數(shù)組進(jìn)行第1操作。 整體復(fù)雜度M^2NLog(N)

第二種：

• 通過計(jì)算所有數(shù)的最大值和最小值，二分平均數(shù) 
• 遍歷所有數(shù)組找最接近平均數(shù)的數(shù)。整體復(fù)雜度Log(H)*Log(N)*M

@rick-IEG應(yīng)用研究▼

有個(gè)想法不知道行不行：

先合并有序數(shù)組，O(N)，同時(shí)紀(jì)錄合并后有序數(shù)組的源數(shù)組的index（染色）；然后開始滑動(dòng)窗口，使得窗口內(nèi)染色數(shù)等于數(shù)組數(shù)，滑的時(shí)候更新方差

@mcsh-PCG開發(fā)工程師▼

(1) 八皇后問題

• 回溯發(fā)遍歷取前 N-1 元素求平均 a，算好方差和平均值
• 使用二分查找Arr[N]，最左邊、最右邊、命中，未選中居中選左右兩個(gè)，更新上面方差和平均值，這部分可優(yōu)化計(jì)算

(2) 樓上 rick 提到滑動(dòng)窗口法，需要枚舉窗口內(nèi)的組合

如果是10 個(gè)數(shù)組，每組 10 個(gè)元素，按順序 1-100，滑動(dòng)窗口滑不動(dòng)，算法復(fù)雜度惡化為窮舉

@looker-PCG開發(fā)工程師▼

有個(gè)二分想法，直接二分方差結(jié)果

• 取int_max作為初始方差，遍歷每個(gè)數(shù)組，每個(gè)數(shù)組取一個(gè)接近的數(shù)值計(jì)算方差
• 后續(xù)用這個(gè)結(jié)果繼續(xù)二分得到下一個(gè)結(jié)果，繼續(xù)遍歷每個(gè)數(shù)組取一個(gè)接近的數(shù)值重新計(jì)算方差
• 重復(fù)第二步，退出二分路徑

@匿名小伙▼

從網(wǎng)上搜到一個(gè)類似的題，題目里只有3個(gè)數(shù)組。如果是多個(gè)，估計(jì)就更麻煩了

貼下大致思路：要從三個(gè)數(shù)組里取x,y,z，使得方差最小，就是找三個(gè)離得最近的數(shù)。因此我們固定一個(gè)數(shù)組，去另外兩個(gè)數(shù)組中，一個(gè)數(shù)組尋找第一個(gè)大于等于它的數(shù)字，另一個(gè)去尋找第一個(gè)小于等于它的數(shù)字。一共是三個(gè)數(shù)組，因此一共有六種組合。

以一種組合來舉例，假設(shè)x<=y<=z，就需要遍歷第二個(gè)數(shù)組（遍歷復(fù)雜度O(n)），然后在第一個(gè)數(shù)組里找到比y小的最大值x，在第三個(gè)數(shù)組里找到比y大的最小值z（二分查找O(logn)）。時(shí)間復(fù)雜度O(nlogn)