0

我有一个相当大的 int[] 使用 . 排序Arrays.sort()。我需要从数组中删除重复的元素。

这个问题源自 sedgewick 的算法书 1.1.28

1.1.28 删除重复项。修改 BinarySearch 中的测试客户端以在排序后删除白名单中的所有重复键。

我试图创建一个 noDupes() 方法，它接受一个 int[] 并返回一个 int[] 并删除了重复项

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

如果您对数组进行了排序并且想要删除重复项，我认为您不需要为此使用二进制搜索。

当您对数组进行排序时，重复的元素将彼此相邻。

例如 Array = {9,8,9,1,2,5,2,5,1} 排序后 Array = {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.
}

将仅在一次通过中删除重复项

于 2013-06-11T09:39:10.153 回答
0

这应该有助于：

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

nodupes 数组超出范围。

注意：我不确定您使用的逻辑是否最适合该问题。但这应该可以解决您的异常。

于 2013-06-11T09:36:11.757 回答
0

此代码将为您提供帮助。

public Integer[] removeDuplicates(Integer[] input){
        Integer[] arrayWithoutDuplicates = null;
        Set<Integer> set = new LinkedHashSet<Integer>();
        for(int i : input){
            set.add(i);
        }
        arrayWithoutDuplicates = (Integer[]) set.toArray();
        return arrayWithoutDuplicates;
}
于 2013-06-11T10:24:30.017 回答