CODEWITHSUNDEEP
c#arraysalgorithmdata-structures
Pritam Karmakar
Pritam Karmakar

Reputation: 2801

Delete Duplicate from an Array

I need to delete duplicate entries from an array, but can't use any new data structures and the same array should return only distinct elements. 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 believe I have solved the problem, but I need your opinion on whether it is a good algorithm or if I need to change something.

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

Upvotes: 0

Views: 1546

Answers (3)

JPvdMerwe
JPvdMerwe

Reputation: 3363

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.

Upvotes: 1

Olexiy
Olexiy

Reputation: 1084

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.

Upvotes: 3

Olexiy
Olexiy

Reputation: 1084

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

Upvotes: 3

Related Questions