找到最短的時間中位數在數組

我有一個數組可以說a = { 1,4,5,6,2,23,4,2}; 現在我必須要找到的陣列位置中位數爲2〜6（奇總而言），所以我做了什麼，我已經採取a[1]到a[5]在arr[0]到arr[4]然後我已經排序它，並且寫作arr[2]作爲中位數。找到最短的時間中位數在數組

但這裏每次我從一個數組輸入值到另一個數組，以便我的初始數組的值保持不變。其次，我已經排序，所以這個過程幾乎是**time**。所以我想知道是否有什麼辦法可以以不同的方式去做less my computation time。

任何網站，要了解的內容，內容以及如何操作？

來源

2012-06-16 Sudhanshu Gupta

你如何排序數組？ – Evans

以及我使用內置的算法 –

如果您在同一陣列上執行多個查詢，那麼你可以使用線段樹。它們通常用於進行範圍最小/最大值和範圍總和查詢，但您可以將其更改爲範圍中值。

具有n個區間的集合的段樹使用O（n log n）存儲並且可以在O（n log n）時間內構建。範圍查詢可以在O（log n）中完成。在範圍線段樹中位數的

實施例：

您建立從下往上的線段樹（從上向下的更新）：

    [4] 
     [2]      [6] 
[0,1]  [3]   [5]   [7] 
0  1  2  3  4  5  6  7

：由節點覆蓋

    [5] 
     [3]      [7] 
[1,2]  [4]   [6]   [8] 
1  2  3  4  5  6  7  8

指數

一種用於中位數爲4-6範圍內的索引查詢會下降值的路徑：

    [4] 
          [5] 
0  1  2  3  4  5  6  7

否則爲中值的搜索，就知道在查詢（3）和在該範圍內中值總元件的數量將是第二元件（索引5）。所以你基本上是在搜索包含該索引的第一個節點，該索引是具有值[1,2]（索引0,1）的節點。

做了搜索範圍3-6的中位數是一個比較複雜一點，因爲你必須尋找兩個指標（4,5），這正好都在同一個節點。

    [4] 
           [6] 
          [5] 
0  1  2  3  4  5  6  7

Segment tree

Range minimum query on Segment Tree

來源

2012-06-16 18:08:37 Justin

+1，如果在同一個陣列上進行多個查詢，這是要走的路。 – ffao

@ ffao，justin，你能告訴更多關於如何在分段樹上進行範圍中值查詢的內容嗎？ – 2147483647

@ A.06我加了一個範圍最小值的例子，但它可以很容易地適應範圍中值。 – Justin

有可能找到中位數沒有排序 O（n）時間;算法這樣做被稱爲selection algorithms。

來源

2012-06-16 16:15:31

很好的答案。爲了澄清，通常使用的那些（如'std :: nth_element'）是O（n）預期時間，而不是O（n）最壞情況時間。這種O（n）最壞情況時間算法在實踐中通常很慢。 –

更新我的評論。 [看起來有很多技巧可以實現良好的實際運行時間和O（n）最差的運行時間。]（http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968）很高興看到哪個實現使用這些。 –

要找到少於9個元素的數組的中值，我認爲最有效的是使用排序算法，如插入排序。複雜性很差，但對於這樣一個小數組，由於諸如快速排序等更好算法的複雜性，插入排序非常有效。做你自己的基準測試，但我可以告訴你插入排序比使用shell排序或快速排序更好。

來源

2012-06-16 16:21:15 ouah

使用std::nth_element從<algorithm>是O（N）：

nth_element(a, a + size/2, a + size); 
median = a[size/2];

來源

2012-06-16 16:56:22 Mark

注意：這是一個變異算法，它可能會重新排列其他項目。 –

但是因爲它扭曲了陣列，我不得不復制數組，我必須排序，它花費了很多時間，我可以做些什麼來解決這個問題 –

對於具有偶數個元素的數組不適用。 –

我認爲最好的方法是使用計數數組的第k最大元素的中位數算法的中位數。你可以在這裏找到算法的總體思路：Median of Medians in Java，在wikipedia上：http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm或者只是瀏覽互聯網。可以在實現過程中進行一些常規改進（避免在選擇特定數組的中位數時進行排序）。但是，請注意，對於數量少於50個元素的數組，使用插入排序比使用中位數算法更有效。

來源

2012-06-16 18:35:39

找到最短的時間中位數在數組

回答

相關問題