話題背景

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

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

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

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

鵝廠工程師的看法

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

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

評論回復(fù)：

@bin·IEG

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

@aaron·WXG

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

似乎不對，這是反例：

[[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)前指針的最小值，而是每個指針的下一個值的最小值，這樣能保證移動后的平均值影響最小

這個case看起來是ok的

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

假如:

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

兩種方式： 

第一種：

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

第二種：

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

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

有個想法不知道行不行：

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

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

(1) 八皇后問題

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

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

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

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

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

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

@匿名小伙▼

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

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

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