陣列平衡點

解決此問題的最佳方法是什麼？一個N元素數組A的平衡點是一個索引i，使得較低索引上的所有元素都具有值< = A [i]並且較高索引上的所有元素都具有高於或等於A [i]的值。陣列平衡點

例如，給定：

A [0] = 4 A [1] = 2 A [2] = 7 A [3] = 11 A [4] = 9

的一個正確的解決方案是：2. A [2]下的所有元素都小於A [2]，A [2]之後的所有元素都大於A [2]。我想到的一個解決方案是O（nsquare）解決方案。有沒有更好的解決方案？

來源

2011-03-22 all_by_grace

出現的想法是O（nsquare）解決方案，遍歷數組，然後執行第二次迭代以檢查它是否滿足條件。 – 2011-03-22 21:56:23

只是想添加一個觀點，平衡點可能不存在給定的整數數組。例如，可以採用按降序排列的任意整數數組，即[4,3,2,1,0]。 – Srikanth 2011-03-22 23:27:13

開始假設A[0]是一個極。然後開始走陣列;將每個元素A[i]依次與A[0]進行比較，並且還跟蹤當前最大值。

只要你找到一個i這樣A[i] < A[0]，你知道A[0]不再是一個極點，並推而廣之，既不可以在任何元素直至幷包括A[i]。所以現在繼續走，直到找到下一個大於當前最大值的值。這隨後成爲新提出的極點。

因此，爲O（n）溶液！

在代碼：

int i_pole = 0; 
int i_max = 0; 
bool have_pole = true; 
for (int i = 1; i < N; i++) 
{ 
    if (A[i] < A[i_pole]) 
    { 
     have_pole = false; 
    } 
    if (A[i] > A[i_max]) 
    { 
     i_max = i; 
     if (!have_pole) 
     { 
      i_pole = i; 
     } 
     have_pole = true; 
    } 
}

來源

2011-03-22 21:59:09

謝謝。你認爲我還有其他的檢查嗎？ – 2011-03-22 22:10:34

如果'A = {0,2,1,3,5,4，...}'，你走到最後並確定'A [0]'是一個極點。但你對其他元素一無所知，所以你必須回溯到'A [1]'並重新開始。在這個數組中，每個第三個元素都是一個極點，以這種方式找到它們需要O（n²）。 – aaz 2011-03-22 22:28:41

這仍然是錯誤的。對於輸入：[9，5，4，3，2，8]，它將返回索引4（其值爲2）。實際上2的左側的所有元素都是較大的，這違反了條件 – 2011-03-22 22:32:14

如果你想知道所有的極點，一個爲O（n log n）的的解決辦法是創建數組的排序副本，並期待看到你在哪裏得到匹配的值。

編輯：對不起，但是這並不實際工作。一個反例是[2, 5, 3, 1, 4]。

來源

2011-03-22 22:15:49 Neil

+1：好主意！ – 2011-03-22 22:53:45

創建一個雙鏈表，如該列表的第i個節點包含A[i]和i。在元素增長的同時遍歷此列表（計算這些元素的最大值）。如果有一些A[bad] < maxSoFar它不能是MP。刪除它並向後移動刪除元素，直到找到A[good] < A[bad]或到達列表的頭部。繼續（以maxSoFar爲最大值），直到您到達列表的末尾。結果列表中的每個元素都是MP，每個MP都在此列表中。複雜性是爲O（n）由於最大的步驟是按降序排列進行 - 向前n步驟和n清除量。

更新

哦，我，我糊塗「任何」與「天天」，在問題的定義:)。

來源

2011-03-22 23:03:42 hoha

使兩個輔助陣列，每個陣列具有一樣多的元素的輸入陣列，稱爲MIN和MAX。 MAX中的每個元素M都包含來自0..M的輸入中所有元素的最大值。 MIN的每個元素M包含M..N-1輸入中所有元素的最小值。

對於每個元素的輸入陣列的M個，其值與在MIN和MAX中的相應的值。如果INPUT [M] == MIN [M]和INPUT [M] == MAX [M]，那麼M是平衡點。

建築MIN需要N個步驟，MAX也是如此。測試數組然後再採取N個步驟。該解決方案具有O（N）複雜性並找到所有平衡點。在排序輸入的情況下，每個元素都是一個平衡點。

來源

2011-03-23 00:22:06 bmcnett

實際上你只需要構建一個數組，因爲你可以在計算其他數組的時候測試這個數組，因此你不需要保留計算結果。 – Neil 2011-03-24 19:49:25

是的，這也是我要做的第一個優化。 – bmcnett 2011-03-24 21:21:48

您可以結合bmcnett和Oli的答案儘快找到所有的杆子。

std::vector<int> i_poles; 
i_poles.push_back(0); 
int i_max = 0; 
for (int i = 1; i < N; i++) 
{ 
    while (!i_poles.empty() && A[i] < A[i_poles.back()]) 
    { 
     i_poles.pop_back(); 
    } 
    if (A[i] >= A[i_max]) 
    { 
     i_poles.push_back(i); 
    } 
}

如果您想避免重新分配，您可以使用預分配大小爲N的數組。

來源

2011-03-24 20:15:15 Neil

構建輔助MIN和MAX數組的一個優點是，假設無限並行性，由於min和max是關聯運算符，算法具有O（logN）複雜性。今天大多數計算機通過GPU呈現10,000多種並行方式，並且這種增長速度比摩爾定律快。 – bmcnett 2011-03-24 22:21:06

回答

相關問題