0

如果一个数组包含 1,7,7,3,6 并且如果用户询问第二大元素是什么，则输出应该是 7（而不是 6），因为重复值被视为不同。
这是我的代码。
我正在使用确定性搜索来找到合适的 pivot 。
它的复杂度是 O(n)。
我被我的代码生成的错误困住了。
请帮帮我。

import java.util.Random;
import java.util.Scanner;


public class deven  {

    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        int len=in.nextInt();
        int n=in.nextInt();
        int array[]=new int[len];
        for (int i = 0; i < len; i++) {
            array[i]=in.nextInt();
        }


        System.out.println(select(array,len,n));

    }

    static int below[];
    static int above[];
    static int pivot;
    static int i;
    static int j;
    static int x;
    static int y;
    static int index;
    static Random rand=new Random();
    static int select(int array[],int len,int n){

        if(len==1)
            return array[0];
        pivot=pivot(array, len);

        below=new int[len];
        above=new int[len];
        //System.out.println("Block");
        x=0;
        y=0;
        int temp=0;
        for(i=0;i<len;i++){
            if(array[i]>pivot){
                below[x++]=array[i];
            }
            else if(array[i]<pivot){
                above[y++]=array[i];
            }
            else {
                if(temp!=0){
                below[x++]=array[i];
            }
                temp=1;
        }
        }

        i = x;
           j = len - y;
        if(n<i) return select(below,x,n);
        else if(n>=j) return(select(above,y,n-j));
        else  return(pivot);



    }

    static int pivot(int array[],int len){
        if(len==1){
            return array[0];
        }
        int numOfGroups=len/5;
        if(len%5!=0){
            numOfGroups++;
        }

        int setOfMedians[]=new int[numOfGroups];
        for (int i = 0 ; i < numOfGroups ; i++)
        {
            int[] subset;
            if(array.length % 5 > 0)
            {
                if (i == numOfGroups - 1)
                {
                    subset = new int[array.length % 5];
                }
                else
                {
                    subset = new int[5];
                }
            }
            else
            {
                subset = new int[5];
            }
            for (int j = 0; j < subset.length ; j++)
            {
                subset[j] = array[5*i+j];
            }
            setOfMedians[i] = median(subset);
        }

        int goodpivot=select(setOfMedians, numOfGroups,numOfGroups/2 );
        return goodpivot;

    }
    static int median(int[] array)
    {
        if (array.length == 1)
        {
            return array[0];
        }
        int smallerCount = 0;
        for (int i = 0 ; i < array.length ; i++)
        {
            for (int j = 0 ; j < array.length ; j++)
            {
                if (array[i] < array[j])
                {
                    smallerCount++;
                }
            }
            if (smallerCount == (array.length - 1)/2)
            {
                return array[i];
            }
            smallerCount = 0;
        }
        return -1; 
    }


}

输入
6
3
1 2 3 1 2 3
输出 

Exception in thread "main" java.lang.StackOverflowError  
    at deven.pivot(deven.java:99)  
    at deven.select(deven.java:34)  
    at deven.pivot(deven.java:102)  
    at deven.select(deven.java:34)  
    at deven.select(deven.java:59)  
    at deven.select(deven.java:59)  
    at deven.select(deven.java:59)
4

2 回答 2

1

问题是你的中位数方法。它不应该返回 -1。在中值方法的最后一行，而不是

return -1;

将其更改为

return array[rand.nextInt(array.length)];

请注意，此修复只是尝试修复您遇到的错误。从中位数方法不返回中位数的意义上说，这不是一个好的解决方法。我认为应该重构应用程序。修复的想法实际上是在pivot方法中。一个好的支点是中位数。但是，如果您无法有效地找到中位数，那么枢轴可以是数组中的随机选择。

更新：

让我们修复中位数方法：

static int median(int[] array) {
    if (array.length == 0) {
        throw new IllegalArgumentException("array cannot be empty.");
    }
    
    int mid = array.length / 2;
    for (int candidate : array) {
        int lower = 0;
        int higher = 0;
        for (int value : array) {
            if (value < candidate) {
                lower++;
            }
            else if (value > candidate) {
                higher++;
            }
        }
        if (lower <= mid && higher <= mid) {
            return candidate;
        }
    }
    throw new IllegalStateException();
}
于 2012-07-08T12:55:24.057 回答
1

如果您在更小的计数之外还维护了一个 equalsCount，那么当您的候选值也是重复值时，您应该能够检测到它是否是中位数。

（解释）

当您的中值方法意外失败时，您似乎故意将 -1 作为无效值返回。抛出某种异常会更合适，但你真正想要的是它永远不会达到那个点。

当中位数重复时，您的算法将失败。例如，在集合 { 1, 2, 2, 2, 3 } 中，2 是明显的中位数，但从来没有一个点恰好有 2 个值“小于”任何正在验证的值。

如果您同时计算较小和相等的值，那么如果您当前的测试通过，或者较小的计数小于中点且较小的 + 相等计数大于中点，则您可以知道您的候选人是中位数。

于 2012-07-08T14:52:52.503 回答