Javaの 'nth_element'と同等の機能は何ですか？

Question

ソートされた配列を取得する必要はありません。ちょうどn番目の要素の値です。例えば、配列

a = [20, 5, 1, -3] 

与えられた私はC++で

nth_element(a,2) = 1 

を照会できるようにしたいのですが、これを行うことができます機能std::nth_elementがあります。同等のJava関数はありますか？

ありがとうございます！

Answer 1

Java標準ライブラリには、C++ nth_elementアルゴリズムと同等のものは含まれていません。あなたが得る最も近いものはCollections.sortです。

また、この機能の独自のバージョンを実装することもできます。標準の並べ替えを実行してCollections.sortを呼び出すことでnth_elementを実装できますが、これは時間要件によっては遅すぎる可能性があります。 選択アルゴリズムとthe Wikipedia page on the subjectには、いくつかの良い例があります。この並べ替えを実行するための多くの特殊なアルゴリズムがあります。経験的に、最も速いアルゴリズムはquickselectと呼ばれ、クイックソートアルゴリズムに基づいています。予想されるO（n）時間に実行されますが、病理学的に不良な入力についてはO（n ）に低下します。有名な（そして悪名高い複雑な）アルゴリズムがありますが、時には最悪の場合O（n）で実行されますが、実際に使用されることを妨げる高い定数係数を持つmedian-of-mediansアルゴリズムと呼ばれます。

希望すると便利です。

私はあなたが、このような何かを、それを実装するために持っていると思うJavaでは

Answer 2

：ここ

Integer nth_smallest_element(Integer[] originalArray, n) { 
    if (n >= originalArray.length) 
     throw new RuntimeException("Invalid index"); 
    // Don't pass in your array, if you don't want it to be modified. Instead add them all later. 
    List<Integer> copyList = new ArrayList<Integer>(); 
    copyList.addAll(originalArray); 
    Collections.sort(copyList); 
    return copyList.get(n); 
} 

Answer 3

がnth_elementのJava実装である：

class Nth_element 
{ 
    static void nth_element_helper2(double[] arr, int beg, int end) 
    { 
     for(int i = beg + 1; i < end; i++) 
     { 
      for(int j = i; j > beg; j--) 
      { 
       if(arr[j - 1] < arr[j]) 
        break; 
       double t = arr[j]; 
       arr[j] = arr[j - 1]; 
       arr[j - 1] = t; 
      } 
     } 
    } 

    static void nth_element_helper(double[] arr, int beg, int end, int index) 
    { 
     if(beg + 4 >= end) 
     { 
      nth_element_helper2(arr, beg, end); 
      return; 
     } 
     int initial_beg = beg; 
     int initial_end = end; 

     // Pick a pivot (using the median of 3 technique) 
     double pivA = arr[beg]; 
     double pivB = arr[(beg + end)/2]; 
     double pivC = arr[end - 1]; 
     double pivot; 
     if(pivA < pivB) 
     { 
      if(pivB < pivC) 
       pivot = pivB; 
      else if(pivA < pivC) 
       pivot = pivC; 
      else 
       pivot = pivA; 
     } 
     else 
     { 
      if(pivA < pivC) 
       pivot = pivA; 
      else if(pivB < pivC) 
       pivot = pivC; 
      else 
       pivot = pivB; 
     } 

     // Divide the values about the pivot 
     while(true) 
     { 
      while(beg + 1 < end && arr[beg] < pivot) 
       beg++; 
      while(end > beg + 1 && arr[end - 1] > pivot) 
       end--; 
      if(beg + 1 >= end) 
       break; 

      // Swap values 
      double t = arr[beg]; 
      arr[beg] = arr[end - 1]; 
      arr[end - 1] = t; 

      beg++; 
      end--; 
     } 
     if(arr[beg] < pivot) 
      beg++; 

     // Recurse 
     if(beg == initial_beg || end == initial_end) 
      throw new RuntimeException("No progress. Bad pivot"); 
     if(index < beg) // This is where we diverge from QuickSort. We only recurse on one of the two sides. This is what makes nth_element fast. 
      nth_element_helper(arr, initial_beg, beg, index); 
     else 
      nth_element_helper(arr, beg, initial_end, index); 
    } 

    static double nth_element(double[] arr, int index) 
    { 
     nth_element_helper(arr, 0, arr.length, index); 
     return arr[index]; 
    } 

    public static void main(String[] args) 
    { 
     double[] arr = { 9, 7, 1, 5, 6, 4, 3, 2, 8, 0, 10 }; 
     if(nth_element(arr, 5) == 5) 
      System.out.println("seems to work"); 
     else 
      System.out.println("broken"); 
    } 
}