Move duplicate numbers at end in integer array

Question

I want to move all duplicate numbers at the end of array like this.

{4,1,5,4,3,1,6,5}

{4,1,5,3,6,4,1,5} also i want to know number of dups. that i will use to resize array. here is the code i tried but this code is not compatible when i insert more than 2 dups at starting.

static void RemoveRepeated(ref int[] array)
    {
        int count = 0; bool flag;
        for (int i = 0; i < array.Length; i++)
        {
            flag = true;
            for (int j = i+1; j < array.Length-1; j++)
            {
                if (array[i] == array[j] )
                {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                        if (flag)
                        {
                            count++;
                            flag = false;
                        }
                }
            }
        }
        Array.Resize(ref array,array.Length-count);
    }

Thanks in advance :)

Just a question. why not `array=array.Distinct().ToArray()` ? you prefer a way without using LINQ or what ? — Magesh Kumaar, Oct 09 '15 at 06:15
@AbdulRehman i just want dups at the end order doesn't matter. — Praveen Deewan, Oct 09 '15 at 17:34
@MageshKumaar i don't want to use any library class/function.and linq. Otherwise i can do directly with HashSet easily. — Praveen Deewan, Oct 09 '15 at 17:36
Why do you title your post "move duplicate numbers at end of array" but your intent is to obtain a distinct list? — , Oct 09 '15 at 17:45

score 2 · Answer 1 · edited May 23 '17 at 11:58

2

A good solution will be to use a fitting data-structure. It will not fix your algorithm but replace it. Here a HashSet<T> is perfect. A HashSet<T> remove itself all duplicate. Check the msdn for more informations.

Demo on .NETFiddle

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var array = new int[]{ 4,1,5,4,3,1,6,5 };

        RemoveRepeated(ref array);

        foreach (var item in array)
            Console.WriteLine(item);
    }

    static void RemoveRepeated(ref int[] array)
    {
        array = new HashSet<int>(array).ToArray();
    }
}

By the way you don't really need ref here. I would remove it and change void RemoveRepeated(ref int[] array) to int[] RemoveRepeated(int[] array). See ref parameter or return value?

edited May 23 '17 at 11:58

Community

1
1

answered Oct 09 '15 at 06:16

aloisdg

22,270
6
85
105

This will remove the duplicats, but you forgot that he needs to count them. – Jannik Oct 09 '15 at 06:26
@Jannik He need to count them only to resize his array. With my solution, you don't have to count it at all. You just don't need it. – aloisdg Oct 09 '15 at 06:27
Ah, okay, I thought he needed it, because he asked for it explicitly. :) – Jannik Oct 09 '15 at 06:29
@aloisdg i don't want to use HashSet or any collection classes. – Praveen Deewan Oct 09 '15 at 17:40
2

@PraveenDeewan Why do you waste your time? You are already using a collection called array. If you just trying to prove yourself, why don't your write your code in assembler? Or better yet start from the beginning and design your own processor so you don't have a dependency on Intel or AMD. – Oct 09 '15 at 17:49
@Sam sir i understand, there are many things dot net has provided already but sometimes there is some limitations to use such kind of classes. and if i write assembly code then possibly i were not asked this question. – Praveen Deewan Oct 09 '15 at 18:05
1

The specific questions you asked were a) how move duplicates to the end of the array and b) how to count the number of dupes. Presumably you want a distinct list (which you did not ask for but myself and others have been kind enough to point you in the right direction). What limitations does .net impose and why are these limitations not specified in your question? – Oct 09 '15 at 18:15

score 1 · Answer 2 · answered Oct 09 '15 at 06:16

What you are doing is equivalent to leaving only the unique elements in their original order. Here is simpler way to do this:

    static void RemoveRepeated(ref int[] array)
    {
        HashSet<int> seen = new HashSet<int>();
        List<int> newArray = new List<int>(array.Length);

        foreach(int x in array)
        {
            if(!seen.Contains(x))
            {
                seen.Add(x);
                newArray.Add(x);
            }
        }

        array = newArray.ToArray();
    }

score 0 · Answer 3 · answered Oct 09 '15 at 06:22

Don't use an array here. You can try to (just one example) group a List<int> and Count() all groups that have more than one element. When you have the count, you can use Distinct() to get only the distinct elements.

In my opinion, resizing an array like this is always a very bad idea.

Edit:

Well, like the other answers already stated, a HashSet is a even better way of doing it.

score 0 · Answer 4 · 2015-10-09T06:43:38.250

0

Try this:

class Program
{
    static void Main(string[] args)
    {
        int[] ints = {4,1,5,4,3,1,6,5};

        var query = ints.GroupBy(x => x).OrderBy(x => x.Count()).Select(x => x);


        // print ordered array showing dupes are last
        query.ToList().ForEach(x => Console.WriteLine(x.Key.ToString()));

        // Get number of dupes
        int dupeCount = query.Where(x => x.Count() > 1).Count();

        // put unique items into a new array
        var newArray = query.Where(x => x.Count() == 1).Select(x => x.Key).ToArray();

        // put distinct items into an array
        var distinctArray = ints.Distinct().ToArray();

        Console.ReadKey();   
    }
}

Edit: Added distinct elements

edited Oct 09 '15 at 06:43

answered Oct 09 '15 at 06:31

Please don't use `.ToList().ForEach()`. [“foreach” vs “ForEach”](http://blogs.msdn.com/b/ericlippert/archive/2009/05/18/foreach-vs-foreach.aspx). – aloisdg Oct 09 '15 at 06:33
For the purpose it was used its fine but thanx for noticing. – Oct 09 '15 at 06:35

Enigmativity · Answer 5 · 2015-10-10T04:12:06.763

If you want to move the duplicates to the end of array (but preserve order) you can do this:

static void RemoveRepeated(ref int[] array)
{
    var lookup = array.ToLookup(x => x);
    var maxdupes = lookup.Select(x => x.Count()).Max();

    var reordered =
        Enumerable
            .Range(0, maxdupes)
            .SelectMany(x => lookup.SelectMany(y => y.Skip(x).Take(1)))
            .ToArray();

    Array.Copy(reordered, array, reordered.Length);
}

This would turn { 4, 1, 5, 4, 3, 1, 6, 5 } into { 4, 1, 5, 3, 6, 4, 1, 5 }

You can easily get the number of duplicates by doing this:

lookup
    .Select(x => new
    {
        Value = x.Key,
        Count = x.Count(),
    });

This returns:

score 0 · Answer 6 · answered Oct 09 '15 at 06:42

 class Program
{
    static void Main(string[] args)
    {
        int[] arr = new int[] { 4, 1, 5, 4, 3, 1, 6, 5 };
        RemoveRepeated(ref arr);
        foreach (int i in arr)
        {
            Console.WriteLine(i);
        }
        Console.ReadKey();
    }

    private static void RemoveRepeated(ref int[] array)
    {
        int count =0;
        for (int i = 0; i < array.Length; i++)
        {
            for (int j = i + 1; j < array.Length; j++)
            {
                if (array[i] == array[j])
                {
                    int temp = array[j];
                    count++;
                    for (int k = j; k < array.Length-1; k++)
                    {
                        array[k] = array[k + 1];
                    }
                    array[array.Length - 1] = temp;
                    j = array.Length;
                }
            }
        }
        Array.Resize(ref array, array.Length - count);
    }
}

Move duplicate numbers at end in integer array

6 Answers6