Как реализовать рандомизированный алгоритм O (n) для нахождения медианы несортированного массива в Java?

Question

У меня есть этот код для нахождения медианы несортированного массива за O (n) ожидаемое время, O (n ^ 2) в худшем случае.Я использую long, потому что хочу иметь возможность хранить длинные значения.

public class Randomized {

    long kthSmallestHelper(long arr[], long l, long r, long k) 
    { 
        if (k > 0 && k <= r - l + 1) 
        { 
            long pos = randomPartition(arr, l, r); 

            if (pos-l == k-1) 
                return arr[(int)pos]; 

            if (pos - l > k - 1) 
                return kthSmallestHelper(arr, l, pos - 1, k);

            return kthSmallestHelper(arr, pos + 1, r, k - pos + l - 1); 
        } 
          return Integer.MAX_VALUE; 
    } 

    void swap(long arr[], long i, long j) 
    { 
        long temp = arr[(int)i]; 
        arr[(int)i] = arr[(int)j]; 
        arr[(int)j] = temp; 
    } 

    long partition(long arr[], long l, long r) 
    { 
        long x = arr[(int)r], i = l; 
        for (long j = l; j <= r - 1; j++) 
        { 
            if (arr[(int)j] <= x) 
            { 
                swap(arr, i, j); 
                i++; 
            } 
        } 
        swap(arr, i, r); 
        return i; 
    } 

    long randomPartition(long arr[], long l, long r) 
    { 
        long n = r - l + 1; 
        long pivot = (long)(Math.random()) * (n - 1); 
        swap(arr, pivot + 1, r); 
        return partition(arr, l, r); 
    } 

    long kthSmallestRandom(long arr[], long k){
        return kthSmallestHelper(arr, 0, arr.length - 1, k);

    }

}

Но когда я запускаю его

    long[] array =  {12, 3, 5, 7, 4, 19, 26}; //median is 7
    Randomized rand = new Randomized();
    System.out.println(rand.kthSmallestRandom(array, (array.length + 1)/2));

Это неверно (возвращает 4).

Моя идея состояла в том, чтобы использовать эту версию k-го наименьшего числа, чтобы сказать, что я хочу (length / 2) -го наименьшего, который является медианой.

Что не так с моей идеей или реализацией?

Answer 1

В вашей функции kthSmallestHelper есть небольшая ошибка в этой строке:

if (pos-l == k-1) 
    return arr[(int)pos];

При возврате используется неверный индекс. Попробуйте pos-l+1 вместо pos (и приведите к int). Это возвращает k-й элемент, который был только что отсортирован в правильное место в массиве.

Answer 2

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

Answer 3

Я не в том месте, чтобы запустить его, но кажется, что многое может быть не так в данный момент.

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

Этот код должен быть прокомментирован намного больше, чтобы мы могли сказать, что вы пытаетесь сделать в каждой точке. ТАКЖЕ похоже, что если вы поменяете местами в отсортированном порядке, это будет O (nlogn), поскольку вы не можете сортировать по линейному времени. И почему вы не можете использовать k == 0 для k-го наименьшего помощника?