Непонимание медианы алгоритма медианов для нахождения k-го элемента

Question

Ниже приведен мой код для того, чтобы попытаться понять медиану алгоритма медианов (используя блоки размером 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]; 
} 

Answer 1

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

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

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

Answer 2

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