No duplicates in an array

Question

 void RemoveDups(){
    int f=0;
    for(int i=1;i<nelems;i++){
        if(arr[f]==arr[i]){
            for(int k=i;k<nelems;k++)
            {
                arr[k]=arr[k+1];
            }
            nelems--;
        }
        if(i==(nelems+1)){
            f++;
           i=f+1; //increment again
        }
    }
}

This is the logic i have written to remove duplicate elements from an array ,but this is not working at all ?what changes i should make to make it work? or you people have better logic for doing the same considering time complexity.and i don't want to use built-in methods to achieve this.

Answer 1

int end = input.length;

    for (int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            if (input[i] == input[j]) {
                int shiftLeft = j;
                for (int k = j + 1; k < end; k++, shiftLeft++) {
                    input[shiftLeft] = input[k];
                }
                end--;
                j--;
            }
        }
    }

Answer 2

You have two options, C# has the Distinct() Linq expression that will do this for you (Missed the Java tag), however if you need to remove items, have you thought about sorting the list first, then comparing the current item to the previous item and if they're the same, remove them. It would mean your diplicate detection is only ever running through the array once.

If you're worried about sort you could easily implement an efficient bubble sort or somthing to that effect

Answer 3

I think you can use Set Collection

copy all the values to an HashSet and then using Iterator access the Values

Set<Integer> hashset= new HashSet<Integer>();

Answer 4

You never decrease i after You compared for examlpe arr[0] to arr[5], You never will test arr[1] == arr[2]

You need to start a new loop (i) after You've incremented f.

try

for(int f=0;f<nelems-1;f++)
{
  for(int i=f+1;i<nelems;i++)
  {
   ...
  }
}

with this nested for loop you can compare every two element of the array.

Answer 5

a good start is to eliminate duplicate elements without shrinking the array which is done lastly:

public class run2 extends Thread {

public static void main(String[] args) {
    int arr[] = { 1, 2, 2, 3, 5, 6, 5, 5, 6, 7 };

    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] == -1)
                j++;

            if (arr[i] == arr[j])
                arr[j] = -1;
        }
    }

    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + ",");
    }
    System.out.println();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == -1) {
            for (int j = i; j < arr.length; j++) {
                if (arr[j] != -1) {
                    arr[i] = arr[j];
                    arr[j] = -1;
                    break;
                }

            }

        }
    }

    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + ",");
    }
}

}

Answer 6

As far as I understood from your code,you are comparing each value starting from index 0 to the rest of the element and when you see the element which is located at index f your are trying to shift the entire array and decrementing the size of array(nelems).Look at line no. 11

if(i==(nelems+1)){
            f++;
            i=f+1;

The problem is when i is set to f+1,i will again be incremented in the for loop for the next iteration.So basically i starts comparing from f+2.And also you are comparing i with (nelems+1) considering the case when nelems decremented but you are not considering the case when i reaches the end without decreasing nelems in that case i will never be equale to (nelems+1).Now considering your logic you could do 2 things.

1.Here is your working code.

for(int i=1;i<nelems;i++){
        if(arr[f]==arr[i]){
            for(int k=i+1;k<nelems;k++)
            {
                arr[k-1]=arr[k];
            }
            if(i==(nelems-1)){
                f++;
                i=f;
            }
            nelems--;   
        }
        if(i==(nelems-1)){//end of the loop
           f++;
           i=f; //increment again
    }
}

2.You could use an outer for loop alternatively that will increment the f value once the inner for is completed.

void RemoveDups(){
    for(int f=0;f<nelems;++f){
        for(int i=1;i<nelems;i++){
            if(arr[f]==arr[i]){
                for(int k=i;k<nelems;k++)
                    arr[k]=arr[k+1];
                nelems--;
            }
         }
       }
    }

Now your problem is solved but the time complexity of your code will be(O(N^3)).

Now instead of shifting the entire array at line 4,you could just swap the arr[f] with last element.

if(arr[f]==arr[i]){
        swap(arr[f],arr[nelems-1]);   
        nelems--;
  }

it will reduce the time complexity from O(N^3) to O(N^2).

Now I'll suggest you my method

1.just sort the array.It will be done in O(NlogN). 2.now using one for loop you can get what do you wanted.

void RemoveDups(){
        int k=0,i;
            for(i=1;i<nelems;++i){
             while(arr[i]==arr[i-1])
                 ++i;
             arr[k++]=arr[i-1];
           }
    arr[k++]=arr[i-1];
}

Now basically you got an array of size k,which contains non repeated element in sorted order and the time complexity of my solution is O(NlogN).

Answer 7

Adapt this code :

public static int[] removeDuplicates(int[] numbersWithDuplicates) {

        // Sorting array to bring duplicates together      
        Arrays.sort(numbersWithDuplicates);     

        int[] result = new int[numbersWithDuplicates.length];
        int previous = numbersWithDuplicates[0];
        result[0] = previous;

        for (int i = 1; i < numbersWithDuplicates.length; i++) {
            int ch = numbersWithDuplicates[i];

            if (previous != ch) {
                result[i] = ch;
            }
            previous = ch;
        }
        return result;
}