Удаление дубликатов из отсортированного int [] с использованием binarysearch

Question

У меня довольно большой int [], который сортируется с использованием Arrays.sort() .. Мне нужно удалить повторяющиеся элементы из массива.

Этот вопрос возникает из алгоритмов книги Седжвика 1.1.28

1.1.28 Удалить дубликаты. Измените тестовый клиент в BinarySearch, чтобы удалить любые удаленные ключи в белом списке после сортировки.

Я попытался создать метод с noDupes(), который принимает в межд [] и возвращает INT [] с дубликатами удалены

ранг() методы из code.which Седжвика делает бинарный поиск

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); 

Я получаю неожиданную output..even AFTE г 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) 

Я не мог понять, что я делаю wrong..can кто-то помочь?

Answer 1

Я хотел бы сделать это таким образом

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; 
} 

Answer 2

просто добавить все значения массива в HashSet он автоматически удалит дубликаты и дает уникальные значения, а затем снова преобразовать его в массив, который вы требовали

Answer 3

Это должно помочь:

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

nodupes массив выходит из строя.

Примечание: Я не уверен, что логика, которую вы используете, является наилучшим решением проблемы. Но это должно решить ваше исключение.

Answer 4

Если у вас есть сортировка массива, и если вы хотите удалить дубликаты, я думаю, вам не нужно использовать для этого двоичный поиск.

При сортировке массива дублирующие элементы будут смежными друг с другом.

E.g. Array = {9,8,9,1,2,5,2,5,1} После сортировки Array = {1,1,2,2,5,5,8,9,9}

Вы можно использовать следующий способ для удаления дубликатов (INPLACE)

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. 
} 

будет удалить дубликаты за один проход только

Answer 5

Этот код поможет вам.

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; 
}