noDups()method to remove all duplicates from the array

Question

It removes the duplicates in the Array but skips one item near the end. Can anybody help me fix this?

The output would be like this:

77 44 55 33 55 22 88 11 33 66 33 

Removing duplicates...

77 44 55 22 88 11 33 

It skipped the '66' when it should be printed.

Here's my code: 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

You should not modify the indices while you iterate over the array, else you will see some weird result. The iteration would certainly skip some elements, as their indices are not the one that is supposed to be.

Suppose you are iterating the array like this:

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

Now you remove the element at index 0. Then all the remaining elements will shift left, but i will keep on moving forward. After deleting element at index 0, the array structure is like this:

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

See, the next element processed will be 5, and not 2. That is why your code is skipping an element.

---

You can solve this issue by iterating the array backwards, which will not modify the indices of remaining elements to be processed. And oh, you don't need nested for loop. Just single for loop will do the task.

Modify your loop as such:

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())
        }
    }

Having said that all, consider using a Set for this task. This is why Set is there in Java API. It automatically removes the duplicate elements.

Answer 2

You should try this one. In JDK we have many such utility classes.

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

One problem that you have is that you call nElems--; twice - once in delete (which is fair enough) and once in noDups, immediately after the call to delete. You should remove the latter.

A second problem is the one that Rohit identified.

Answer 4

I'm new to programming but please see below for my attempt. I think it works.

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

}