Найти К-й по величине элемент (Java)

Question

Нужно реализовать данный алгоритм:

выбираем из списка наибольший элемент и помещаем его в конец списка. В оставшейся части выбираем наибольший элемент и помещаем его на второе место от конца списка. Продолжаем процедуру до тех пор, пока не дойдем до К-го по величине элемента.

Также дан псевдокод:

FindKthLargest(list,K,N)
list список для просмотра
N число элементов в списке
К порядковый номер по величине требуемого элемента
for i=1 to К do
largest=list[1]
largestLocation=1
for j=2 to N-(i-1) do
if list [j]>largest then
largest=list [j]
largestLocation=j
end if
end for
Swap(list[N-(i-1)],list[largestLocation])
end for
return largest

Вот, что вышло у меня:

package algorithm;
public class Main {
public static void main(String[] args) {
     int[] arr =  { 12, 3, 5, 7, 4, 11, 26 };
     System.out.print("K'th largest element is " + findKthLargest(arr, 7, 3));
}
public static int findKthLargest(int[] list, int N, int K) {
    for(int i=0; i<K; i++) {
        int largest = list[1];
        int largestLocation=1;
        for(int j=1; j<N-(i-1); j++) {
            if(list[j]>largest) {
                largest=list[j];
                largestLocation = j;
            }
        }
        int temp = list[N-(i-1)];
        list[N-(i-1)] = list[largestLocation];
        list[largestLocation] = temp;
        return largest;
    }
    return 0;
}
}

Но он не хочет работать, выдавая ошибку Index 7 out of bounds for length 7 на 6 и 13 строке. Никак не могу понять, как заставить его работать.

Answer 1

Когда первый раз попадаете во второй цикл, вы пытаетесь пробежать больше элементов, чем есть в массиве

for(int j=1; j<N-(i-1); j++)

здесь N = 7, i = 0, получается 7 - (0 - 1) = 8

Как исправить?

-1 необходимо убрать из условия цикла
заменить 1 на 0 при инициализации largest и largestLocation
исправить условия при перемещении элементов массива чтобы не выходить за его размер

public static int findKthLargest(int[] list, int N, int K) {
    for(int i=0; i<K; i++) {
        int largest = list[0];
        int largestLocation=0;
        for(int j=1; j<N-i; j++) {
            if(list[j]>largest) {
                largest=list[j];
                largestLocation = j;
            }
        }
        int temp = list[(N-1)-i)];
        list[(N-1)-i] = list[largestLocation];
        list[largestLocation] = temp;
        return largest;
    }
    return 0;
}

Answer 2

Основные ошибки в том, что последний элемент имеет индекс N-1, а также в том, что выполняется возврат из метода после первой же итерации.

Также следует отметить, что параметр N в методе излишний, так как фактически это list.length. Кроме того, можно передавать массив list как vararg, тогда упростится вызов метода:

public static int findKthLargest(int K, int ... list) {
    int N = list.length;
    for(int i = 0; i < K; i++) {
        int largest = list[0];
        int largestLocation = 0;
        for(int j = 1; j < N-i; j++) {
            if(list[j] > largest) {
                largest=list[j];
                largestLocation = j;
            }
        }

        int temp = list[N-i-1];
        list[N-i-1] = list[largestLocation];
        list[largestLocation] = temp;
    }
    return list[N - K];
}

Тест:

int K = 3;
System.out.println(K + "-й наибольший элемент: " + findKthLargest(3, 12, 3, 5, 7, 4, 11, 26));

int[] arr =  { 12, 12, 12, 14, 14, 11, 26};
System.out.println(4 + "-й наибольший элемент: " + findKthLargest(4, arr));

Вывод:

3-й наибольший элемент: 11
4-й наибольший элемент: 12

БЛОГ НА HUSL

Найти К-й по величине элемент (Java)

Ответы (2 шт):