Chức năng 'nth_element' tương đương trong Java là gì?

Question

Tôi không muốn có một mảng được sắp xếp, chỉ giá trị của phần tử thứ n. Ví dụ, với các mảng

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

Tôi muốn để có thể truy vấn

nth_element(a,2) = 1 

Trong C++, có một chức năng std::nth_element có thể làm điều này. Có một hàm Java tương đương không?

Cảm ơn!

Answer 1

Java thư viện chuẩn không chứa tương đương với thuật toán C++ nth_element. Gần nhất mà bạn sẽ nhận được sẽ sử dụng Collections.sort.

Ngoài ra, bạn có thể thử thực hiện phiên bản riêng của bạn về chức năng này. Bạn có thể thực hiện nth_element bằng cách thực hiện sắp xếp tiêu chuẩn và gọi Collections.sort, mặc dù tùy thuộc vào yêu cầu về thời gian của bạn có thể quá chậm. Có rất nhiều thuật toán chuyên biệt để thực hiện sắp xếp sắp xếp lại này được gọi là các thuật toán lựa chọn và the Wikipedia page on the subject có một số ví dụ hay. Theo kinh nghiệm, thuật toán nhanh nhất được gọi là quickselect và dựa trên thuật toán quicksort; nó chạy trong thời gian O (n) dự kiến ​​nhưng có thể giảm xuống O (n) cho các đầu vào xấu về bệnh lý. Có một thuật toán nổi tiếng (và nổi tiếng phức tạp) đôi khi được gọi là thuật toán trung bình-trung bình chạy trong trường hợp xấu nhất O (n), nhưng có một yếu tố không đổi cao ngăn cản nó được sử dụng trong thực tế.

Hy vọng điều này sẽ hữu ích!

Answer 2

Trong Java Tôi nghĩ rằng bạn phải thực hiện nó, một cái gì đó như thế này:

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

Đây là một thực hiện Java của nth_element:

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"); 
    } 
}