如何找到N個數字的前半部分的平均值？

給定N個任意整數，如何找到這些數字的上半部分的平均值？是否有O（n）解決方案？如果不能證明這是不可能的？如何找到N個數字的前半部分的平均值？

2010-09-05 Seeker

這個問題是否與編程有關（即使用程序解決這個問題）？ – BoltClock 2010-09-05 09:44:23

我不知道。如果你有方法，你可以給數學公式。它只是一個面試問題。 – Seeker 2010-09-05 09:49:57

這是面試官想知道候選人是否可以將真實世界問題減少到已知算法的問題之一。這通常比能夠背誦算法本身更重要。因此，我很難理解爲什麼這個問題是關閉的話題。 – Accipitridae 2010-09-05 12:52:29

首先，找到給定數組的median（它是takes linear time）。

然後，通過數組並總結所有大於中位數的元素。

統計你總結了多少個元素（M）。如果M < N/2，那麼這意味着幾個等於中值的元素（即N/2 - M）屬於上半部分。添加許多中值。我們需要這種複雜性，因爲我們不知道上半部分有多少箇中間元素（可以有幾個）：如果我們全部採用它們，我們最終可以總結出超過N/2個元素。

現在你有了數組上半部分的總和。除以N/2，就完成了。

來源

2010-09-05 10:27:44

或者代碼可能會更簡單，如果您執行額外的O（n）過程並只計算等於中位數的元素數。這會告訴你在平均數中包含多少等於中間值的元素。 – 2010-09-05 14:18:03

更簡單的是，使用幾乎所有算法來查找中位數也會將輸入列表的分區找到上半部分。因此一旦發現中位數，上半部分的所有元素都已知。 – Accipitridae 2010-09-14 18:30:17

我建議這樣的：

使用快速排序，選擇一些支點。這會將你的列表分割成兩個子列表，一個小於數據透視表，一個比這更大。如果較小子列表的大小爲< = N/2，則計算平均值a1。
如果size == N/2 or size == N/2 -1
您立即完成。

如果不重新劃分更大的子列表，直到總大小爲N/2。

如果大小> N/2分區較小的子列表。

重複所有操作直到完成。

P.S：你不需要排序。

來源

2010-09-05 09:57:37 sud03r

這是'O（n^2）'在最壞的情況下...... – 2010-09-05 10:28:25

您可以使用優先級隊列。將這些元素插入隊列中，保持您已看過多少元素的計數，n。從隊列中提取n/2最大元素到累加器中並計算平均值。

在隊列後面有精心挑選的數據結構，如斐波那契堆，這會給你O(n log n)運行時間，因爲插入是O(1)，並且提取是O(log n)。

不幸的是，您所尋找的不是O（n）運行庫，而是已經實現的數據結構，這會產生非常容易理解的簡單代碼。

來源

2010-09-05 10:18:25

* Finding *在斐波那契堆中，最大值爲O（1），但是*除去*（因此允許第二個到最大值在另一個O（1）中被找到）是O（log n）。如果「insert」和「remove max」在Fibonacci堆中都是O（1），那麼可以使用一個在O（n）中執行比較排序。 – 2010-09-05 14:24:07

你說的很對，很抱歉，我已經編輯了我的答案。那個討厭的nlogn排序的下限！ – 2010-09-05 14:38:45

如果你能找到線性時間的中位數，這顯然可以在線性時間內解決。找到線性時間的中位數是棘手的，但可能的。請參閱例如關於selection algorithms的維基百科文章。

來源

2010-09-05 10:23:45 Accipitridae

如何找到N個數字的前半部分的平均值？

回答

相關問題