Поиск индекса k-го наименьшего элемента в массиве эффективно (итеративный)?

Question

Я хотел бы найти k-й наименьший элемент в массиве, но на самом деле нужен его индекс для моего метода разделения.

Я нашел этот код на этом блоге для поиска -ю наименьший элемент: http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html

Но это только возвращает значение, а не индекс.

У вас есть идеи, как я могу найти его индекс эффективно?

Answer 1

Самый простой способ создать дополнительный indices массив той же длины, заполнить его числами от 0 до length-1 и когда arr массив изменяется, выполняют те же изменения с indices массива. Наконец, верните соответствующую запись из массива indices. Вам даже не нужно понимать оригинальный алгоритм для этого. Вот модифицированный метод (мои изменения отмечены ***):

public static int selectKthIndex(int[] arr, int k) { 
    if (arr == null || arr.length <= k) 
     throw new IllegalArgumentException(); 

    int from = 0, to = arr.length - 1; 

    // ***ADDED: create and fill indices array 
    int[] indices = new int[arr.length]; 
    for (int i = 0; i < indices.length; i++) 
     indices[i] = i; 

    // if from == to we reached the kth element 
    while (from < to) { 
     int r = from, w = to; 
     int mid = arr[(r + w)/2]; 

     // stop if the reader and writer meets 
     while (r < w) { 

      if (arr[r] >= mid) { // put the large values at the end 
       int tmp = arr[w]; 
       arr[w] = arr[r]; 
       arr[r] = tmp; 
       // *** ADDED: here's the only place where arr is changed 
       // change indices array in the same way 
       tmp = indices[w]; 
       indices[w] = indices[r]; 
       indices[r] = tmp; 
       w--; 
      } else { // the value is smaller than the pivot, skip 
       r++; 
      } 
     } 

     // if we stepped up (r++) we need to step one down 
     if (arr[r] > mid) 
      r--; 

     // the r pointer is on the end of the first k elements 
     if (k <= r) { 
      to = r; 
     } else { 
      from = r + 1; 
     } 
    } 

    // *** CHANGED: return indices[k] instead of arr[k] 
    return indices[k]; 
} 

Обратите внимание, что этот метод изменяет исходный массив arr. Если вам не нравится это, добавьте arr = arr.clone() в начале метода.