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;
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment