Delete Duplicate from an Array

Question

Hi,

I received one question "How to delete duplicate entries from an array" Constrain: No new data structure and same array should return only distinct element. So for example If my array is 1,3,3,3,5,55,67,1 then the result should be 1,3,5,55,67

I have solved the problem

    public void DeleteDuplicate(int[] array)
    {
        int l = 0;
        int newPosition = array.Length -1;
        for (int i = 0; i < array.Length; i++)
        {
            for (int j = i + 1; j < array.Length-l; j++)
            {
                if (array[i] == array[j])
                {
                    int temp = array[j];
                    array[j] = array[newPosition];
                    array[newPosition] = temp;
                    newPosition--;
                    l++;
                }
            }
        }
        Array.Resize(ref array, array.Length - l);
    }

I need your opinion whether it is a good algorithm or need to change something.

Thanks, Pritam

Answer 1

Your code is buggy. Try running it against {1, 1, 1} - I think it will return {1, 1}.

Answer 2

In general, the question whether you have to maintain the relative ordering of the elements. For example, whether it is possible to return {1, 2} for input {2, 1, 2, 1}.

If it is allowed, then the fastest solution will be:

• sort input array
• run once through it comparing a[i] with a[i+1] and removing duplicates in O(N)'

The total complexity would be O(N*logN), which is better than N^2 you proposed.

If you must preserve the initial ordering, then I am not ready to propose a solution.

Answer 3

Last time I checked C# allowed you to sort 2 arrays by using one for the comparisons and doing the swaps on both.

Here's what you can do:

• Create an array indices that stores the numbers 0 to N-1.
• Sort array and indices using array as the key.
• Find the duplicates and set the indices of duplicates to N+1.
• Sort array and indices using indices as key.
• Resize the array to the correct size and presto.

This removes duplicates and preserves ordering.