爭論我的算法是正確的，並在範圍內

我正在做一些算法分配，並被問及以下內容：排序O（n）中的元素'r'或'w'的數組，以便'r始終在'w's之前。因此，如果輸入看起來像[w，r，w，r，w，r，w，w]，算法運行後，數組看起來像[r，r，r，w，w，w，w，w ]。爭論我的算法是正確的，並在範圍內

從概念上講，這看起來很清楚。我必須使用兩個邊界變量來保存第一個'w'元素的位置，一個用於最後一個'r'元素。

我的代碼如下：

char[] A = new char[] { 'w', 'r', 'w', 'r', 'w', 'r', 'w', 'w' }; 

int lastRedPosition = A.Length - 1; 
int firstWhitePosition = 0; 

for (int i = firstWhitePosition ; i < A.Length; i++) 
{ 
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position 
    for (int j = lastRedPosition; j > firstWhitePosition; j--) 
    { 
     if (A[j] == 'r') 
     { 
      lastRedPosition = j; 
      break; 
     } 
    } 

    for (int k = firstWhitePosition; k < lastRedPosition; k++) 
    { 
     if (A[k] == 'w') 
     { 
      firstWhitePosition = k; 
      break; 
     } 
    } 

    A[firstWhitePosition] = 'r'; 
    A[lastRedPosition] = 'w'; 
}

現在，我認爲它運行在O（n）的，直觀的，儘管嵌套for循環。這是因爲，總而言之，數組只被遍歷一次。因爲我們正在跟蹤lastRedPosition和firstWhitePosition變量的位置。

但是我發現很難激發這個更正式的，因爲相同的嵌套for循環...有人可以給我一些指向正確的directopm指針？

來源

2013-01-07 Oxymoron

這看起來像一個糟糕的合併排序。 – Woot4Moo

這看起來很像計數排序。 http://www.geekviewpoint.com/java/sorting/countingsort。由於你只有兩個不同的元素，你的時間複雜度是O（n + 2），它是O（n）。那裏的解釋可能會幫助你形式化你的論點。也可以看看你的教科書中的排序參數，並使用它。如果你的文本中沒有計算排序，請查看bucketsort。 –

這不就是quicksort的迭代1嗎？

您從左側掃描，直到您點擊'w'。然後你從右邊掃描直到你點擊'r'。然後你交換這兩個元素並繼續。當兩臺掃描儀走到一起時，您會停止。

這就是O（n）。

編輯：如：

int i = 0, j = n-1; 
while(true){ 
    while(a[i]=='r' && i<n) i++; 
    while(a[j]=='w' && j>0) j--; 
    if (i >= j) break; 
    swap(a[i], a[j]); 
}

來源

2013-01-07 19:27:39

這不正是我所說的嗎？我發現一個錯誤，外部循環應該從'firstWhitePosition'開始，不固定爲0. – Oxymoron

僅僅因爲整個數組只被遍歷一次不會自動使它成爲O（n）。事實是，在最不理想的情況下（這是big-O的定義），整個數組實際上會遍歷兩次，第二次遍歷發生在外部循環內部，使其成爲O（n^2）。

如果你可以保證只有r和w將會在數組中，那麼O（n）方法就是一次遍歷數組，然後計算有多少個r和w，然後自己重建數組。這實際上是2次遍歷使其成爲O（2n），但傳統上這些係數被丟棄。

來源

2013-01-07 19:00:14

嗯。爲什麼'整個數組實際上會被遍歷兩次，使得O（n^2）'成立？那將是2 * N，不是？ –

是的，2N！= N^2。它被獨立遍歷兩次，沒有在另一個遍歷（又名嵌套循環）中遍歷 –

@ AK4749哦，我誤解了你的評論，我看到你在說什麼。我應該在我的措辭中更加清楚。兩種算法實際上都會遍歷兩次，這更多的是第二次遍歷的位置（在外部循環或外部循環內） –

如果將外部循環轉換爲while循環，則運行至firstWhitePosition和lastRedPosition會更容易。很顯然，這兩個變量一起只是遍歷數組。

來源

2013-01-07 19:00:36 Henry

從技術上講，這是O（N）;然而，從性能的角度來看，它是O（2N），意味着它的平均速度是一半。這是因爲你的外部循環每個元素執行一次，而它們之間的內部循環遍歷每個元素，這意味着迭代次數是元素的兩倍。

你有正確的想法，但是如果不是遍歷每個元素的外層循環，只要「知道」所有r都位於所有w的左邊，就停下來了？

換句話說，您從數組的右端掃描r（應該在左邊），從左邊的w（應該在右邊）開始掃描。如果w位於w的左側，則應交換並繼續;但是，如果您的「最後一個」索引位於「第一個w」索引的左側，那麼您已完成並應終止整個功能。相反，你當前的實現繼續循環（和交換）。這是效率低下。按照Henry的建議，我會用一個while循環替換outer for循環，最終的r位於第一個w的左邊。

來源

2013-01-07 19:03:42 KeithS

的第一個問題是，你的算法是不正確的。如果數組中只有'w'或僅有'r' s，則仍將外部循環末尾的數組寫入'w'和'r'。

而在這種情況下，您的代碼實際上需要Θ(N²)時間。比方說，一切都是'r'：

char[] A = new char[] { 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r' }; 

int lastRedPosition = A.Length - 1; 
int firstWhitePosition = 0; 

for (int i = firstWhitePosition ; i < A.Length; i++) 
{ 
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position 
    for (int j = lastRedPosition; j > firstWhitePosition; j--) 
    { 
     if (A[j] == 'r') 
     { 
      lastRedPosition = j; 
      break; 
     } 
    }

j是A.length - 1 - i現在。在第一次迭代中，它立即發現了一個'r'，稍後，已經寫入i'w' s到數組的最後一個條目，並且lastRedPosition是第一個的索引，因此except for the first iteration, j`只是遞減一次。

for (int k = firstWhitePosition; k < lastRedPosition; k++) 
    { 
     if (A[k] == 'w') 
     { 
      firstWhitePosition = k; 
      break; 
     } 
    }

firstWhitePosition始終爲0。k遞增，直到它變得lastRedPosition沒有找到'w'，所以firstWhitePosition不改變。因此k遞增A.length - 1 - i次。

總和i合計~N²/2增量k。

A[firstWhitePosition] = 'r'; 
    A[lastRedPosition] = 'w'; 
}

您必須檢查是否A[firstWhitePosition]實際上是'w'和A[lastRedPosition]實際上'r'。如果沒有，你就完成了。你的外循環應該檢查firstWhitePosition < lastRedPosition。

來源

2013-01-07 20:09:24

通過數組一次，計算'r'和'w'的數量，將它們存儲爲numberR和numberW。將非'r'和非'w'字符存儲在名爲S2的StringBuffer中。
打印numberR'r到一個新的StringBuffer S1。將S2附加到S1。將'w'的數字W追加到S1。
從StringBuffer中獲取字符數組。

總成本：O（n）的

來源

2013-01-08 22:03:54

不是一個就地算法 – Oxymoron

爭論我的算法是正確的，並在範圍內

回答

相關問題