Метод noDups() для удаления всех дубликатов из массива

Question

Он удаляет дубликаты в массиве, но пропускает один элемент ближе к концу. Кто-нибудь может мне помочь исправить это?

Вывод будет выглядеть так:

77 44 55 33 55 22 88 11 33 66 33 

Удаление дубликатов...

77 44 55 22 88 11 33 

Он пропустил '66' когда это должно быть напечатано.

Вот мой код:HighArray.java

class HighArray {
private long[] a;
private int nElems;

public HighArray(int max) {
    a = new long[max];
    nElems = 0;
}

public boolean find(long searchKey) {
    int j;
    for(j=0; j<nElems; j++)
        if(a[j] == searchKey)
            break;
    if(j == nElems)
        return false;
    else
        return true;
}

public void insert(long value) {
    a[nElems] = value;
    nElems++;
}

public boolean delete(long value) {
    int j;
    for(j=0; j<nElems; j++)
        if( value == a[j] )
            break;
    if(j==nElems)
        return false;
    else {
        for(int k=j; k<nElems; k++)
            a[k] = a[k+1];
        nElems--; 
        return true;
    }
}

public void noDups() {
    System.out.println("\nRemoving duplicates...");

    for(int i = 0; i<nElems; i++) {
        for(int j = i+1; j<nElems; j++) {
            if (a[i] == a[j]) {
                delete(a[i]);
                nElems--;
            }
        }
    }
    //return duplicates;
}

public void display(){
    for(int j=0; j<nElems; j++)
        System.out.print(a[j] + " ");
    System.out.println("");
}

}

HighArrayApp.java

class HighArrayApp {

public static void main(String[] args) {

    int maxSize = 100;
    HighArray arr;
    arr = new HighArray(maxSize);

    arr.insert(77);
    arr.insert(55);
    arr.insert(99);
    arr.insert(44);
    arr.insert(55);
    arr.insert(33);
    arr.insert(55);
    arr.insert(22);
    arr.insert(88);
    arr.insert(11);
    arr.insert(33);
    arr.insert(00);
    arr.insert(66);
    arr.insert(33);

    arr.display();

    int searchKey = 35;
    if( arr.find(searchKey) )
        System.out.println("Found " + searchKey);
    else
        System.out.println("Can’t find " + searchKey);

    arr.delete(00);
    arr.delete(55);
    arr.delete(99);

    arr.display();

    arr.noDups();
    arr.display();
}

}

Answer 1

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

Предположим, вы итерируете массив следующим образом:

0 1 2 3 4 5  // indices
1 2 5 6 7 8  // array elements
^
i            // current position of i

Теперь вы удаляете элемент по индексу 0, Тогда все остальные элементы сместятся влево, но i будет продолжать двигаться вперед. После удаления элемента с индексом 0 структура массива выглядит следующим образом:

0 1 2 3 4   // indices
2 5 6 7 8   // array elements
  ^
  i         // current position of i (Will move from 0 to 1)

Смотрите, следующий обработанный элемент будет 5, и не 2, Вот почему ваш код пропускает элемент.

---

Вы можете решить эту проблему, перебирая массив в обратном направлении, что не приведет к изменению индексов оставшихся элементов, подлежащих обработке. И вам не нужно вложенное в цикл. Просто один цикл for сделает задачу.

Измените ваш цикл так:

for(int i = nElems; i > 0; i--) {
        if (a[i] == a[i + 1]) {
            delete(a[i]);
         // nElems--; // Not needed here. (You're already doing this in delete())
        }
    }

Сказав, что все, рассмотреть вопрос об использовании Set для этой задачи. Вот почему Set есть в Java API. Он автоматически удаляет дубликаты элементов.

Answer 2

Вы должны попробовать это. В JDK у нас много таких служебных классов.

public static void main(String[] args){

    Long [] a = {77l, 44l, 55l, 33l, 55l, 22l, 88l, 11l, 33l, 66l, 33l};

    Set<Long> set=new HashSet<>(Arrays.asList(a));
    System.out.println(set);
}

Answer 3

Одна из проблем, с которыми вы сталкиваетесь, заключается в том, что вы звоните nElems--; дважды - один раз в delete (что достаточно справедливо) и один раз в noDupsсразу после звонка delete, Вы должны удалить последний.

Вторая проблема - та, которую определил Рохит.

Answer 4

Я новичок в программировании, но, пожалуйста, ознакомьтесь с моей попыткой ниже. Думаю, работает.

      public void noDups(){       
  int i;
  int j;

  for(i = nElems-1;i>=0;i--){
     for(j = i-1;j>=0;j--){
        if(a[i]==a[j]){
            delete(a[j]);
        }
     }
  }

}