0

配列に 1,7,7,3,6 が含まれていて、ユーザーが 2 番目に大きい要素を尋ねた場合、重複する値は別個のものとして扱われるため、出力は (6 ではなく) 7 になるはずです。
これは私のコードです。
私は決定論的検索を使用して適切なピボットを見つけています。
その複雑さは 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

smallCount に加えて equalsCount を保持している場合は、候補値が重複している場合にその値が中央値であるかどうかを検出できるはずです。

（説明）

中央値メソッドが予期せず失敗した場合、無効な値として意図的に -1 を返しているようです。何らかの例外をスローする方が適切ですが、本当に必要なのは、その時点に到達しないことです。

中央値が重複している場合、アルゴリズムは失敗します。たとえば、セット { 1, 2, 2, 2, 3 } では、2 が明らかな中央値ですが、検証される値のいずれかよりも「小さい」値が正確に 2 つ存在するポイントはありません。

より小さい値と等しい値の両方をカウントする場合、現在のテストに合格するか、小さい方のカウントが中間点よりも小さく、かつ小さい + 等しいカウントが中間点よりも大きい場合に、候補が中央値であることがわかります。

于 2012-07-08T14:52:52.503 に答える
1

問題はあなたの中央値法です。-1 を返すべきではありません。中央値法の最後の行では、代わりに

return -1;

に変更します

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

この修正は、発生したエラーを修正する試みにすぎないことに注意してください。中央値メソッドが中央値を返さないという意味では、これは適切な修正ではありません。アプリケーションをリファクタリングする必要があると思います。修正のアイデアは、実際にはピボット メソッドにあります。良いピボットは中央値です。しかし、中央値を効率的に見つけることができない場合、ピボットは配列の中からランダムに選択される可能性があります。

アップデート：

中央値法を修正しましょう。

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 に答える