查找未排序數組中的第k個最小元素

我試圖實現以下僞代碼。我只需要使用邏輯分區來做到這一點。查找未排序數組中的第k個最小元素

Procedure SELECT(k,S) 
{ if |S| =1 then return the single element in S 
    else { choose an element a randomly from S; 
      let S1,S2,and S3 be he sequences of elements in S 
      less than, equal to, and greater than m, respectively; 
     if |S1| >=k then return SELECT(k,S1) 
      else 
       if (|S1| + |S2| >=k then return m 
       else return SELECT(k-|S1|-|S2| , S3); 
     } 
}

這是我在它的企圖到目前爲止：

public static int select(int k, int[] s, int arrayLeft, int arrayRight) { 
    if (s.length == 1) { 
     return s[0]; 
    } else { 
     Random rand = new Random(); 
     int right = rand.nextInt(arrayRight) + arrayLeft; 
     int m = s[right]; 
     int pivot = partition(s, arrayLeft, right); // pivot = |s1| 
     if (pivot >= k) { 
      return select(k, s, arrayLeft, pivot - 1); 
     } else { 
      // Calculate |s2| 
      int s2Length = 0; 
      for (int i = pivot; s[i] == m; i++) { 
       s2Length++; 
      } 
      if (pivot + s2Length >= k) { 
       return m; 
      } else { 
       int s3Left = pivot + s2Length; 
       return select(k - pivot - s2Length, s, s3Left + 1, s.length); 
      } 
     } 
    } 
} 

// all elements smaller than m are to the left of it, 
// all elements greater than m are to the right of it 
private static int partition(int[] s, int left, int right) { 
    int m = s[right]; 
    int i = left; 
    for (int j = left; j <= right - 1; j++) { 
     if (s[j] <= m) { 
      swap(s, i, j); 
      i++; 
     } 
    } 
    swap(s, i, right); 
    return i; 
} 

private static void swap(int[] s, int i, int j) { 
    int temp = s[i]; 
    s[i] = s[j]; 
    s[j] = temp; 
}

我select方法不返回實際的第k個最小元素。分區方法只在小於m的元素上正常工作。在m右側的數組部分，有任何值的元素。我該如何解決？我在網上看到的所有解決方案都與我的方法相同。任何幫助表示讚賞！

來源

2017-04-25 Flaom

我很困惑。在僞代碼中它說什麼關於重新排序數組？因爲如果你要重新排序，你可以使用排序算法，然後返回數組的第k個元素... – Mark

該算法應該比完整排序更快。你必須以某種方式表示S1，S2和S3，通過重新排序數組並不是最難的事情。 –

您需要學習使用調試器。 –

我不確定你的代碼應該如何工作的細節，但我想我已經發現了一些可疑的問題。

首先，我認爲你應該精確地說明你的方法的有效參數以及它如何使用arrayLeft和arrayRight。寫一個Javadoc評論並說明這一點。這會讓你和其他人更容易爭論代碼中的正確和錯誤。

這是錯誤的：

if (s.length == 1) {

你傳入同一陣列通過你所有的遞歸調用，所以如果它沒有從一開始就長1（一個微不足道的情況下），它永遠不會有長度1.改用arrayLeft和arrayRight來確定要考慮的元素數量。

這行看起來不正確：

 int right = rand.nextInt(arrayRight) + arrayLeft;

如果arrayLeft是10和12 arrayRight，它可能會產生高達21我做了以下行觀察的ArrayIndexOutOfBoundsException一度因爲right指出陣列外部。

在此行中的註釋不正確，可能會導致您對代碼錯誤論點：

 int pivot = partition(s, arrayLeft, right); // pivot = |s1|

的pivot從partition()返回的重新排序後的指數m。我認爲正確的說法是pivot == arrayLeft + |s1|。請檢查一下自己。

我進一步認爲，您不應該通過right作爲上述調用中的最後一個參數，而是arrayRight。此錯誤可能是您觀察的原因partition()將任何值留在m的右側。

您可能風險的ArrayIndexOutOfBoundsException這裏太：

  for (int i = pivot; s[i] == m; i++) {

您應該添加一個附加條件像i <= arrayRight或i < s.length。

最後，這看起來錯在我的眼前：

   return select(k - pivot - s2Length, s, s3Left + 1, s.length);

我想到的是：

   return select(k - pivot - s2Length, s, s3Left, arrayRight);

但請用自己的知識進行檢查。我特別懷疑arrayRight。

來源

2017-04-25 11:14:27

查找未排序數組中的第k個最小元素

回答

相關問題