話題背景

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

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

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

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

鵝廠工程師的看法

@jk-CDG基礎平臺負責人▼

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

評論回復：

@bin·IEG

這個移動難度比較大，無法保證向較大的方向移動方差的函數的單調性

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

這個case看起來是ok的

@zhenle-IEG開發工程師▼

假如:

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

兩種方式： 

第一種：

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

第二種：

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

@rick-IEG應用研究▼

有個想法不知道行不行：

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

@mcsh-PCG開發工程師▼

(1) 八皇后問題

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

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

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

@looker-PCG開發工程師▼

有個二分想法，直接二分方差結果

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

@匿名小伙▼

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

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

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