使用减少并征服找到中位数

Question

你好，我遇到以下问题，我似乎1）不完全了解partition方法2）我无法用我的代码查明问题所在。

问题描述：递归地使用reduce-and-conquer在三个或更多整数的数组中找到中位数。我们将使用仅考虑从给定索引开始到另一个索引结束的部分数组的约定。这样，递归调用可以遍历数组的任何部分。初始调用将传入索引0，并将索引传递到最后一个元素。

rAcMedian（[2，1，3，-2，8]，0，4）→2rAcMedian（[-4，6，2]，0，2）→2rAcMedian（[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

您可以尝试合并对数组排序并取中间值（偶数长度为n / 2，奇数长度为n / 2 +1）。

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