Friday, February 25, 2011

Java program to De duplicate array in O(n) time

public int[] deduplicate(int[] numbers,int N)
{
//Number from 1 to N are stored in an array of size N
//De-duplicate the array without using extra space.
//Algo should be O(n)
int val=0;

for(int i=1;i<=N;i++) { val=Math.abs(numbers[i]); //The fact that a number X appeared once - is represented by //changing the sign of the value at arr[X]. //So if arr[X] is -ve that means X is duplicate. if(numbers[val]>0)
numbers[val]=numbers[val]*-1;
else
{
numbers[i]=N+1;
}


}
return numbers;

}

No comments: