Самый эффективный способ поиска n-го наивысшего числа в массиве?

Question

Мне интересно, если это самый эффективный способ найти n-е число в несортированном массиве. То, что я сделал, было сортировать с помощью mergeSort, затем найти индекс n-го наивысшего числа. Я думаю, что это более эффективно, чем большинство поисков, но я не совсем уверен, что .....

import java.util.Arrays; 
public class ThirdHighest { 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int [] a = new int[]{3,5,6,7,8,2,1,10,9}; 
    System.out.print(Arrays.toString(a)); 
    mergeSort(a); 
    System.out.print(Arrays.toString(a)); 
    System.out.print(nHighestValue(a, 3)); 

} 
public static void mergeSort(int[] arr) { 
    if(arr.length > 1) { 
     int lengthLeft = arr.length/2; 

     int [] left = Arrays.copyOfRange(arr, 0, lengthLeft); 
     int [] right = Arrays.copyOfRange(arr, lengthLeft, arr.length); 
     mergeSort(left); 
     mergeSort(right); 
     merge(arr, left, right); 
    } 
} 
public static void merge(int[] result, int[] left, int[] right){ 
    int l1 = 0; 
    int r2 = 0; 
    while(l1 < left.length || r2 < right.length) { 
     if(l1 == left.length) { 
      result[l1+r2] = right[r2]; 
      r2 += 1; 
     } else if(r2 == right.length){ 
      result[l1+r2] = left[l1]; 
      l1 += 1; 
     } else if(left[l1] < right[r2]) { 
      result[l1 + r2] = left[l1]; 
      l1 += 1; 
     } else { 
      result[l1+r2] = right[r2]; 
      r2 += 1; 
     } 
    } 
} 
public static int nHighestValue(int[] a, int n) { 
    int index = a.length - n; 
    return a[index]; 

} 

} 

Answer 1

Рандомизированный quickselect алгоритм работает в среднем случае сложности O (n). Практически очень редко бывает O (n^2). Он использует статистическую функцию quicksort

Answer 2

Поиск низкий или высокий из unodrered данных может быть сделано в O (N), а @ alitereralmind демонстрирует.

Нахождение N-го наивысшего (по запросу) сложнее, поскольку вам нужно отслеживать лучших кандидатов. Это превращает сканирование в сортировку вставки N-глубины со значениями, которые не входят в верхнюю часть N, выпадающую из конца. Хотя это может быть более эффективным, чем полноценная сортировка, я не уверен, что это стоит дополнительных усилий по кодированию проблем с нормальным размером ... особенно если повторный запрос может быть снова выпущен, и первоначальный вид можно повторно использовать.