¿Cuál es la función equivalente de 'nth_element' en Java?

Question

No quiero obtener una matriz ordenada, solo el valor del n-elemento. Por ejemplo, dada la matriz

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

Me gustaría ser capaz de consultar

nth_element(a,2) = 1 

En C++, hay una función std::nth_element que puede hacer esto. ¿Hay una función Java equivalente?

Gracias!

Answer 1

La biblioteca estándar de Java no contiene un equivalente del algoritmo C++ nth_element. Lo más cercano que obtendrá sería usar Collections.sort.

Alternativamente, podría intentar implementar su propia versión de esta función. Puede implementar nth_element haciendo una clasificación estándar y llamando al Collections.sort, aunque dependiendo de los requisitos de tiempo, esto puede ser demasiado lento. Hay muchos algoritmos especializados para realizar este tipo de reordenamiento que se llaman algoritmos de selección y the Wikipedia page on the subject tiene varios buenos ejemplos. Empíricamente, el algoritmo más rápido se llama quickselect y se basa en el algoritmo de quicksort; se ejecuta en el tiempo esperado de O (n) pero puede degradarse a O (n) para entradas patológicamente malas. Existe un algoritmo famoso (y notoriamente complejo) a veces llamado el algoritmo de la mediana de las medianas que se ejecuta en el peor de los casos O (n), pero tiene un alto factor constante que impide que se use en la práctica.

Espero que esto ayude!

Answer 2

En Java Yo creo que hay que ponerla en práctica, algo como esto:

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

Aquí es una implementación de Java de 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"); 
    } 
}