Niezrozumienie mediany algorytmu mediana dla znalezienia elementu k

Question

Poniżej znajduje się mój kod do próby zrozumienia mediany algorytmu median (za pomocą bloków wielkości 5). Rozumiem, jak zdobyć mediany danych wejściowych, ale nie jestem pewien, jak zakodować blok, aby kontynuować rekursję danych wejściowych, dopóki nie uzyska się median. Następnie po uzyskaniu tej mediany, nie jestem pewien, jak użyć go jako osi obrotu, aby wyrzucić bezużyteczne informacje, aby podzielić dane wejściowe. getMediansArray zwraca tablicę o wielkości sufitu (input.length/5) i getMedians po prostu zwraca medianę z tablicy (używane tylko w tablicach o długości < = 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

Mediana mediana to po prostu algorytm szybkiego wyboru (http://en.wikipedia.org/wiki/Quickselect) poprawiony. Podczas gdy funkcja szybkiego wyboru ma O (n) średni czas złożoności, może zwolnić do O (n^2) w celu uzyskania trudnych danych wejściowych.

Co zrobić po znalezieniu mediany median to nic innego jak iteracja algorytmu szybkiego wyboru. Mediana median ma ładną właściwość, która zawsze będzie większa niż 30% elementów i mniejsza niż 30% elementów. Gwarantuje to, że szybki wybór przy użyciu mediany median dla osi obrotu będzie przebiegał w najtrudniejszej złożoności czasu O (n). Patrz: http://en.wikipedia.org/wiki/Median_of_medians

Proponuję rozpocząć od wdrożenia szybkiego wyboru. Gdy to zrobisz, możesz użyć kodu, który już posiadasz, aby wybrać pivot w każdym kroku szybkiego wyboru.

Answer 2

Jeśli dobrze pamiętam (refreshing my memory) Mediana median wybiera przybliżoną medianę. Nie rozumiem, jak można go użyć do wybrania k-tego elementu.