Элемент минимума K с использованием быстрого выбора со случайным поворотом - PullRequest
Новая
       6

Элемент минимума K с использованием быстрого выбора со случайным поворотом

0 голосов
/ 30 сентября 2019

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

Ниже приведена реализация моего метода, 

    static int findKthMin(int[]arr, int n, int k) {
        int l=0 , r=n-1;
        Random random = new Random();
        while(true) {
            int x = random.nextInt(r+1-l) + l; // When using x = r (works correctly)
            int pivot = arr[x];
            int idx = l;
            for(int i=l;i<=r;i++) {
                if(arr[i] < pivot) {
                    int temp = arr[idx];
                    arr[idx] = arr[i];
                    arr[i] = temp;

                    idx++;
                }
            }
            arr[x] = arr[idx];
            arr[idx] = pivot;

            if(idx == k-1) return pivot;

            if(idx > k-1) {
                r = idx-1;
            } else {
                l = idx;
            }
        }
    }

Здесь n - это размермассив и k - это k-й минимальный элемент, который нужно найти.
Код работает нормально, когда я использую x=r.

Я думаю, что что-то не так в условии 

   for(int i=l;i<=r;i++) {
       if(arr[i] < pivot) {
            int temp = arr[idx];
            arr[idx] = arr[i];
            arr[i] = temp;

            idx++;
       }
   }

Но я не могу понять, что не так и как это исправить. Я потратил часы на его отладку и изменение кода, но могу выяснить проблему.

Вот тестовые примеры, которые я пробую, 

6               // n
7 10 4 3 20 15  //arr
3               // k

и, 

5             // n
7 10 4 20 15  // arr
4             // k

В этих тестовых случаях случайный сводный элемент дает любой элемент массива в качестве вывода.
Любой намек на то, что может быть ошибкой, будет очень полезным.

1 Ответ

1 голос
/ 30 сентября 2019

После предложения @Nico мне просто нужно было поменять элемент сводки на последний.
Ниже приведен полный рабочий фрагмент, 

    static int findKthMin(int[]arr, int n, int k) {
        int l=0 , r=n-1;
        Random random = new Random();
        while(true) {
            int x = random.nextInt(r+1-l) + l; // When using x = r (works correctly)

            //Swap random pivot with the last index element
            int temp = arr[x];
            arr[x] = arr[r];
            arr[r] = temp;

            int pivot = arr[r];

            int idx = l;
            for(int i=l;i<=r;i++) {
                if(arr[i] < pivot) {
                    temp = arr[idx];
                    arr[idx] = arr[i];
                    arr[i] = temp;

                    idx++;
                }
            }
            arr[r] = arr[idx];
            arr[idx] = pivot;

            if(idx == k-1) return pivot;

            if(idx > k-1) {
                r = idx-1;
            } else {
                l = idx;
            }
        }
    }
...