0

. を使用してソートされたかなり大きな int[] がありArrays.sort()ます。配列から重複した要素を削除する必要があります。

この質問は、sedgewick の Algorithms book 1.1.28 に由来します。

1.1.28 重複を削除します。BinarySearch のテスト クライアントを変更して、並べ替え後にホワイトリスト内の重複キーを削除します。

int[] を取り、重複を削除して int[] を返す noDupes() メソッドを作成しようとしました

rank() メソッドは sedgewick のコードからのものです。二分探索を行います。

public static int[] noDupes(int[] a){
    Arrays.sort(a);
    int maxval= a[a.length-1];
    int[] nodupes = new int[maxval];
    int i=0;
    for(int j=0;j<a.length;j++){
        int rnk = rank(a[j],nodupes);
        System.out.println(a[j]+" rank="+rnk);
        if (rnk < 0){
            System.out.println(a[j]+" is not dupe");
            nodupes[i] = a[j];
            i++;
        }
    }

    return nodupes;
}
public static int rank(int key,int[] a){
    return rank(key,a,0,a.length-1);
}

public static int rank(int key,int[] a,int lo,int hi){
    if(lo > hi) return -1;
    int mid = lo+(hi-lo)/2;

    if(key < a[mid])return rank(key,a,0,mid-1);
    else if(key > a[mid])return rank(key,a,mid+1,hi);
    else return mid;
}

これをサンプル配列で実行したとき

int[] a =new int[]{2,2,2,3,4,4,5,6};
int[] ret = noDupes(a);

予期しない出力が得られます.2 が nodupes 配列に追加された後でも、既存の要素のランクは -1 です..

2 rank=-1
2 is not dupe
2 rank=-1
2 is not dupe
2 rank=-1
2 is not dupe
3 rank=-1
3 is not dupe
4 rank=-1
4 is not dupe
4 rank=4
5 rank=-1
5 is not dupe
6 rank=-1
6 is not dupe
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
    at ...noDupes(BinSearch.java:85)
    at ...main(BinSearch.java:96)

私は自分が間違っていることを理解できませんでした..誰か助けてもらえますか？

4

5 に答える 5

3

私はこのようにします

public static int[] noDupes(int[] a) {
    Arrays.sort(a);
    int noDupCount = 0;
    for (int i = 0; i < a.length; i++) {
        if (i == 0 || a[i] != a[i - 1]) {
            noDupCount++;
        }
    }
    int[] a2 = new int[noDupCount];
    for (int i = 0, j = 0; i < a.length; i++) {
        if (i == 0 || a[i] != a[i - 1]) {
            a2[j++] = a[i];
        }
    }
    return a2;
}
于 2013-06-11T09:30:30.643 に答える
3

すべての配列値を HashSet に追加するだけで、重複が自動的に削除され、一意の値が得られ、必要な配列に再度変換されます

于 2013-06-11T09:26:34.437 に答える
2

配列がソートされていて、重複を削除したい場合は、バイナリ検索を使用する必要はないと思います。

配列をソートすると、重複した要素が互いに隣接します。

例 配列 = {9,8,9,1,2,5,2,5,1} 並べ替え後 配列 = {1,1,2,2,5,5,8,9,9}

次の方法を使用して、重複を削除できます（インプレース）

int a[] = {sorted array}

for(int i=0,target=0;i<a.length-1;i++) {
  if(a[i]!=a[i+1]) {
     a[target++] = a[i];
  }
}
a[target++] = a[a.length-1];
for(int i=target;i<a.length;i++) {
a[i] = 0; // fill in the values which you don't want.
}

1回のパスのみで重複を削除します

于 2013-06-11T09:39:10.153 に答える
0

これは役立つはずです：

int[] nodupes = new int[a.length];

nodupes 配列が限界を超えています。

注: 使用しているロジックが問題に最適かどうかはわかりません。しかし、これはあなたの例外を解決するはずです。

于 2013-06-11T09:36:11.757 に答える