Непонимание медианы алгоритма медиан для поиска k-го элемента

Ниже приведен мой код для попытки понять алгоритм медианы медиан (с использованием блоков размером 5). Я понимаю, как получить медиану ввода, но я не уверен, как закодировать блок, чтобы продолжать повторять ввод, пока у меня не будет медианы. Затем, получив эту медиану, я не уверен, как использовать ее в качестве опорной точки, чтобы отбросить бесполезную информацию для разделения ввода. getMediansArray возвращает массив размера ceil(input.length/5), а getMedians просто возвращает медиану из массива (используется только для массивов длины ‹= 5).

public static int[] findKthElement(int[] input, int k) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] medians = new int[numOfMedians];
    medians = getMediansArray(input, medians)

    // (1) This only gets the first iteration of medians of the
    // input. How do I recurse on this until I just have one median?

    // (2) how should I partition about the pivot once I get it?
}

public static int[] getMediansArray(int[] input, int[] medians) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] five = new int[5];

    for (int i = 0; i < numOfMedians; i++) {
        if (i != numOfMedians - 1) {
            for (int j = 0; j < 5; j++) {
                five[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        } else {
            int numOfRemainders = input.length % 5;
            int[] remainder = new int[numOfRemainders];
            for (int j = 0; j < numOfRemainders; j++) {
                remainder[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        }
    }
    return medians;
}

public static int getMedian(int[] input) {
    Arrays.sort(input);
    if (input.length % 2 == 0) {
        return (input[input.length/2] + input[input.length/2 - 1]) / 2;
    }
    return input[input.length/2];
}

java arrays algorithm median-of-medians
person Emmanuel Mudiay    schedule 16.04.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Медиана медиан — это просто алгоритм быстрого выбора (http://en.wikipedia.org/wiki/Quickselect) улучшилось. Хотя быстрый выбор имеет среднюю временную сложность O (n), он может замедлиться до O (n ^ 2) для сложного ввода.

То, что вы делаете после нахождения медианы медиан, является не чем иным, как итерацией алгоритма быстрого выбора. Медиана медиан имеет хорошее свойство: она всегда будет больше 30% элементов и меньше 30% элементов. Это гарантирует, что быстрый выбор с использованием медианы медиан для опорной точки будет выполняться с наихудшей временной сложностью O (n). См.: http://en.wikipedia.org/wiki/Median_of_medians

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

person Neithrik    schedule 16.04.2015

arrow_upward
0
arrow_downward

Если я правильно помню (освежаю память), медиана медиан выбирает приблизительное медиана. Я не понимаю, как его можно использовать для выбора k-го элемента.

person Daniel    schedule 16.04.2015
comment
В заголовке запрашивается k-й элемент, а в вопросе — точная медиана. Я хотел бы представить, что мой отзыв конструктивен (хотя и не так информативен, как URL-адрес, на который я ссылаюсь). - person Daniel; 16.04.2015