5個排序陣列的中位數

Question

我想找到5個排序陣列的中位數的解決方案。這是一個面試問題。

我能想到的解決方案是合併5個數組，然後找到中位數[O（l + m + n + o + p）]。

我知道，對於2個相同大小的排序數組，我們可以在log（2n）中完成。 [通過比較兩個數組的中位數，然後拋出每個數組的一半並重復該過程]。 ..查找中位數可以是排序數組中的常量時間..所以我認爲這不是log（n）？ ..這是什麼時間複雜性？

1] 5陣列是否有類似的解決方案。如果陣列的大小相同，那麼是否有更好的解決方案呢？

2]我認爲，因爲這是要求5，會有一些解決方案的N排序數組？

感謝您的指點。

一些澄清/問題，我問回給面試官：
相同長度的陣列
=>沒有
我想會有在陣列
=>是

值的重疊

作爲一個練習，我認爲2個數組的邏輯沒有擴展。這裏是一個嘗試：
應用上面的2個數組的邏輯來說3個數組： [3,7,9] [4,8,15] [2,3,9] ...中位數7,8,3
投擲元素[3,7,9] [4,8] [3,9] ..中位數7,6,6
投擲元素[3,7] [8] [9] ..中間人5,8 ，9 ...
投擲元素[7] [8] [9] .. median = 8 ...這似乎不正確？

排序元件的合併=> [2,3,4,7,8,9,15] =>預期值= 7

Answer 1

（這是您的想法對於兩個陣列的概括。）

如果從查看五個數組中的五個中值開始，顯然整體中位數必須介於五個中值的最小值和最大值之間。

證明是這樣的：如果a是中位數的最小值，而b是中位數的最大值，那麼每個數組的小於一半的元素小於a且小於其元素的一半大於灣結果如下。

所以在包含a的數組中，扔掉小於a的數字;在包含b的數組中，扔掉大於b的數字...但是隻丟棄兩個數組中相同數量的元素。也就是說，如果a是從其數組的起點開始的j個元素，並且b是從其數組的末尾開始的k個元素，則拋棄a的數組中的第一個min（j，k）個元素，並且最後一個min （j，k）個元素。

迭代，直到你總計1或2個元素。

這些操作中的每一個（即查找排序數組的中位數並從數組的開始或結尾丟掉k個元素）是恆定時間。所以每次迭代都是恆定的。

每個迭代從至少一個數組中拋出（超過）一半的元素，並且對於這五個數組中的每一個只能執行log（n）次...因此，整體算法是log（n） 。

[更新]

由於Himadri喬杜裏在評論中指出的那樣，我的解決方案是不完整的;有很多細節和角落案例需要擔心。所以，充實的事情了有點...

對於每個五個陣列的R，定義其「低級位數」爲R [N/2-1]和它的「上部中值」爲R [n/2個]，其中n是數組中元素的數量（數組從0開始索引，併除以2舍入）。

令「一」是最小的低中位數，而「B」是最大的上部中位數。如果有多個數組的最低中位數和/或多個數組的上中位數最大，請選擇不同數組中的a和b（這是這些角落案例中的一個）。

現在，借用Himadri的建議：刪除所有元素，直到和包括它的陣列一個，和所有元素向下和包括它的陣列 B，小心地從兩個陣列取出相同數量的元素。請注意，a和b可能在同一個數組中;但如果是這樣，它們不能具有相同的值，否則我們將能夠從不同的陣列中選擇其中的一個。因此，如果這一步驟結束了從同一個數組的開始和結束中拋出元素，那麼就可以了。只要你有三個或多個陣列

迭代。但是，一旦你只考慮了一兩個數組，你就必須改變你的策略，使其成爲獨佔而不是包容性的;你只擦除高達但不包括和向下但不包括灣只要剩下的一個或兩個數組至少有三個元素（保證你取得進展）就繼續這樣做。

最後，你將減少到幾例，其中最棘手的是剩下的兩個數組，其中之一有一個或兩個元素。現在，如果我問你：「給定一個排序後的數組加上一兩個額外的元素，找到所有元素的中位數」，我認爲你可以在不變的時間內做到這一點。 （同樣，還有一堆的細節敲定，但基本思路是增加一個或兩個元素的數組不「推周圍的中位數」非常多。）

Answer 2

應該很直的應用同樣的想法5陣列。

首先，將問題轉換爲更一般的問題。於N找到k個元素排序陣列

1. 查找（K/N）個元素與二進制搜索每個排序後的數組中，說K1，K2 ...... KN

2. kmin個=分鐘（K1 .. KN），Kmax = max（K1 ... KN）

3. 丟掉所有小於Kmin或大於Kmax的元素，比方說X元素已被丟棄。

4. 現在重複的發現過程（K - X）個排序陣列元素與其餘元素

Answer 3

你不需要做5個陣列的完全合併。你可以做一個合併排序，直到你有（l + n + o + p + q）/ 2個元素，那麼你有中位值。