使用快速选择算法在未排序的数组中查找中位数

Question

我正在此处编写此练习：https://www.hackerrank.com/challenges/find-median。我正在使用快速选择算法但不是用于排序数组。我用它来划分数组并找到 medican。但是我的代码仍然不能正常工作，至少在网站上进行了示例测试。

7
0 1 2 4 6 5 3

我正在尝试查找我的问题，但找不到。在某些情况下，我的代码 return true 结果。例如：

7
0 6 3 5 2 4 1

这是我的代码：

/**
 * file FindMedian.java
 */
import java.util.Scanner;
class Number{
    int n;

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }
}
public class FindMedian {
    public static int partition(int[] a, int low, int high, int n){
        int i=low+1, j= high;
        while (true){
            while(a[i]<a[low]){
                i++;
                if (i==high) break;
            }
            while (a[j]>a[low]){
                j--;
                if (j==low) break;
            }
            if (i>=j)
                break;
            swap(a, i, j);
            i++;
            j--;
        }
        swap(a, low, j);
        return j;
    }
    public static void progress(int[] a, int low, int high,int n, Number i){
        if (low>=high)
            return;
        int j= partition(a, low, high, n);

        if (j==n){
            i.setN(j);
            return;
        }
        else
        if (j>n)
            progress(a, low, j-1, n, i);
        else if (j<n)
            progress(a, j+1, high, n, i);
    }
    public static void swap(int[] a, int i, int j){
        int temp= a[i];
        a[i]= a[j];
        a[j]= temp;
    }

    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int a[]= new int[sc.nextInt()];
        int n= (a.length-1)/2;
        for (int index=0; index< a.length; index++)
            a[index]= sc.nextInt();

        Number i= new Number();
        i.setN(-1);

        progress(a, 0, a.length-1, n, i);

        if (i.getN()!=-1)
            System.out.println(a[i.getN()]);
        else System.out.println("Can't find");
    }
}

请帮助我。提前谢谢你:)

Answer 1

我认为您需要获取枢轴的第 k 个位置，并交叉检查它是否与中位数位于同一位置，方法是根据数组中的变量 low 执行此 "int k=j-low+1;"。例如，第二个索引处的值将是数组中第三小的元素。

同样对于第二次递归调用，因为我们知道中位数在枢轴的右侧（在第 k 个位置），我们期望结果在右侧的第 (n-k) 个位置手边子数组

 public static int progress(int[] a, int low, int high,int n){
        if (low==high)
            return a[low];
        //partition array and return index of pivot
        int j= partition(a, low, high, n);

        //find the kth position of the pivot 
        int k=j-low+1;
        //if the kth position of the pivot is the same as the required ith smallest int return pivot.
        if (k==n){
            return a[j];
        }
        else
        if (n<k)
           return progress(a, low, j-1, n, i);
        else if (n>k)
            return progress(a, j+1, high, n-k, i);
    }

另一件错误的事情是你的主要方法中的这一行：

int n= (a.length-1)/2;

应该改为int n=(a.length+1)/2，因为元素个数为奇数的数组的中位数位于(N+1)/2点（N=a.length）。例如对于具有 7 个元素的数组，中位数应在 (7+1)/2=4th 位置。

使用快速选择算法在未排序的数组中查找中位数

Find Median in unsorted array using Quickselect algorithm

java

algorithm

quicksort