Нахождение медианы с помощью Reduce-and-Conquer

Question

Здравствуйте, у меня возникли проблемы со следующей проблемой, кажется, 1) Не полностью понимаю метод раздел 2) Я не могу точно определить проблему с моим кодом.

Описание проблемы : Найти медиану в массиве из трех или более целых чисел, используя рекурсивное уменьшение и завоевание. Мы будем использовать соглашение о рассмотрении только той части массива, которая начинается с данного индекса и заканчивается в другом. Таким образом, рекурсивный вызов может работать через любую часть массива. Первоначальный вызов передается с индексом 0 и индексом до последнего элемента.

rAcMedian ([2, 1, 3, -2, 8], 0, 4) → 2 РАМЕДИАН ([- 4, 6, 2], 0, 2) → 2 РАМЕДИАН ([4, 2, 48, 1, 50], 0, 4) → 4

Код Дайте мне:

int partition(int[] nums, int begin, int end) {
  int splitPos = begin;
  int pivotValue = nums[begin];
  for(int i=begin+1; i<=end; i++) {
    if(nums[i] > pivotValue) {
      splitPos++;
      swap(nums, i, splitPos);
    }
  }
  swap(nums, begin, splitPos);
  return splitPos;
}

void swap(int[] nums, int pos1, int pos2) {
  int temp = nums[pos1];
  nums[pos1] = nums[pos2];
  nums[pos2] = temp;
}

Это мой код:

public int rAcMedian(int[] nums, int begin, int end) {
  if (begin < end){
    int splitPos = partition(nums, begin, end);

    if (splitPos == end/2) return nums[splitPos];
    if (splitPos > end/2) return nums[rAcMedian(nums, splitPos+1, end)];
    if (splitPos < end/2) return nums[rAcMedian(nums, begin, splitPos-1)];

  }
  return 0;
}

Когда я запускаю код, я получаю следующие ошибки:

Answer 1

Когда вы вызываете partition для массива, вы берете первое значение в массиве как pivotValue . Когда partition закончен, все элементы, оставшиеся от pivotValue , больше, чем pivotValue, все справа меньше или равны.
Возвращаемое целое число - это позиция, в которой заканчивается pivotValue. вверх. Вот пример:

public static void main(String[] args) {
    int[] arr = {4, 3, 1, 7, 5};
    int part = partition(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));   //[5, 7, 4, 3, 1]
    System.out.println(part);   //2
}

На 2 элемента больше, чем pivotValue 4. Из-за этого 4 сместилась на 2 позиции вправо и заканчивается индексом 2, который также возвращается в конце.

Обратите внимание, что я сделал ваши заданные функции стати c, чтобы я мог их использовать.

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

Answer 2

Можно попытаться объединить, отсортировать массив и взять среднее значение (n / 2 для четной длины, n / 2 + 1 для нечетной длины).

https://www.geeksforgeeks.org/merge-sort/