0

注意：这个问题是昨天深夜发布的，没有得到足够的答案。我添加了一些细节并重新发布。

作为一项任务，我的任务是创建中位数排序的中位数，这也可以确定数组的第 n 个最小元素（即排序数组的索引 0 是第一个最小的）。这种类型是递归的，这导致我无法理解它，因为我没有广泛使用递归。

通过拼凑教程和对算法的研究，我已经非常接近成功地创建该方法；但是，我目前返回了错误的值。当我希望它返回索引 0 处的值时，QS(A, 1) 的输入将返回索引 1 处包含的值：

public static int QS(int[] A, int k){

    List<Integer> AList = new ArrayList<Integer>();

    if(k < 1 || k >= A.length){
        System.out.println("Code called because k = "+k);
        return -1;
    }

    for (int i = 0; i < A.length; i++){
            AList.add(A[i]);
    }

    if (AList.size() < 14) {
        Collections.sort(AList);
        return AList.get(k);
    }

    ArrayList<Integer> medians = new ArrayList<Integer>();

    for (int i = 0; i < AList.size() - AList.size() % 7; i = i + 7){
        medians.add(medianFind(AList.subList(i, i + 7)));
    }

    int a = medianFind(medians);
    ArrayList<Integer> left = partitionFind(AList, a, true);
    ArrayList<Integer> right = partitionFind(AList, a, false);
    int[] leftArray = new int[left.size()];
    int[] rightArray = new int[right.size()];

    for(int i = 0; i < left.size(); i++){
        leftArray[i] = left.get(i);
    }

    for(int i = 0; i < right.size(); i++){
        rightArray[i] = right.get(i);
    }   

    if(left.size() + 1 == k){
        return a;
    }
    else if(left.size() > k){
        return QS(leftArray, k);
    }
    else{
        return QS(rightArray, k - left.size());
    }

}

/////////

public static int medianFind(List<Integer> AList) {
    Collections.sort(AList);
    return AList.get(AList.size() / 2);
}

/////////

public static ArrayList<Integer> partitionFind(List<Integer> AList, int b, boolean lessThan) {
    ArrayList<Integer> store = new ArrayList<Integer>();
    for (int element : AList)
        if (element < b && lessThan)
                store.add(element);
        else if (element >= b && !lessThan)
                store.add(element);
    return store;
}

为了将最终返回的索引修改为-1，我很难理解该算法中的递归。我不能简单地进行以下更改：

    if (AList.size() < 14) {     //old 
        Collections.sort(AList);
        return AList.get(k);
    }

    if (AList.size() < 14) {     //new 
        Collections.sort(AList);
        return AList.get(k-1);
    }

因为这有时会导致return QS(rightArray, k - left.size())传递的参数小于 1。我也不认为我可以添加：

if(nothing left to sort){
    return AList.get(k-1) 
}

由于算法的递归性质声明。我已经有一段时间没有成功，并且非常感谢任何关于我应该去哪里解决这个问题的迹象。

4

1 回答 1

1 
//returns the k^th smallest element in the array A for 0<k<A.length  
public static int QuickSelect(int[] A, int k){

        List<Integer> AList = new ArrayList<Integer>();

        if(A.length<k||k<1){
            System.out.println("k out of range, got k: "+k +", but A.length: "+A.length);
            return -1;
        }

        for (int i = 0; i < A.length; i++){
                AList.add(A[i]);
        }

至此我们知道了AList.size()>0，所以得到元素k-1，它是列表中第k小的元素

        if (AList.size() < 14) {
            Collections.sort(AList);
            return AList.get(k-1);
        }

        ArrayList<Integer> medians = new ArrayList<Integer>();


        for (int i = 0; i < AList.size() - AList.size() % 7; i = i + 7){
            medians.add(medianFind(AList.subList(i, i + 7)));
        }

***你忘了找到最后一个AList.size()-( AList.size() % 7)元素的中位数

      int a = medianFind(medians);
            ArrayList<Integer> left = partitionFind(AList, a, true);
            ArrayList<Integer> right = partitionFind(AList, a, false);

添加med变量以计算中位数的出现次数

            int med=AList.size()-(left.size()+right.size())
            int[] leftArray = new int[left.size()];
            int[] rightArray = new int[right.size()];

        for(int i = 0; i < left.size(); i++){
            leftArray[i] = left.get(i);
        }

        for(int i = 0; i < right.size(); i++){
            rightArray[i] = right.get(i);
        }

不完全确定其余部分的逻辑，但我认为以下内容更有意义（请注意，我修改了 PartitionFind）

        if(left.size() >= k){
            return QuickSelect(leftArray, k);
        }
        else if(left.size()+med<k){
            return QuickSelect(rightArray, k-(left.size()+med));
        }
        else{
            return a;
        }

    }

    /////////

    public static int medianFind(List<Integer> AList) {
        Collections.sort(AList);
        return AList.get(AList.size() / 2);
    }

    /////////

注意：我对此进行了修改，以使子问题变得更小（例如，您可以将 b 作为列表中的最大元素，而右数组仍将包含整个列表）

    public static ArrayList<Integer> partitionFind(List<Integer> AList, int b, boolean lessThan) {
        ArrayList<Integer> store = new ArrayList<Integer>();
        for (int element : AList)
            if (element < b && lessThan)
                    store.add(element);
            else if (element > b && !lessThan)
                    store.add(element);
        return store;
    }

让我知道这个是否奏效

于 2017-10-04T22:31:56.810 回答