Wie entferne ich Duplikate aus einem C # -Array?

209

Ich habe mit einem string[]Array in C # gearbeitet, das von einem Funktionsaufruf zurückgegeben wird. Ich könnte möglicherweise in eine GenericSammlung umwandeln, aber ich habe mich gefragt, ob es einen besseren Weg gibt, dies zu tun, möglicherweise mithilfe eines temporären Arrays.

Was ist der beste Weg, um Duplikate aus einem C # -Array zu entfernen?

Lomaxx
quelle
4
Verwenden Sie die Distinct-Erweiterungsmethode.
Kokos
Tatsächlich. Es macht mehr Spaß, wenn das Array bereits sortiert ist - in diesem Fall kann es in O (n) -Zeit vor Ort ausgeführt werden.
David Airapetyan
@ Vitim.us Nein. In meinem Fall ist es nicht einmal ein Array, sondern eine List <string>. Ich akzeptiere jede Antwort, die den Job macht. Vielleicht ist es ein Schock, es auf Papier machen zu müssen.
AngryHacker

Antworten:

427

Sie könnten möglicherweise eine LINQ-Abfrage verwenden, um dies zu tun:

int[] s = { 1, 2, 3, 3, 4};
int[] q = s.Distinct().ToArray();
Jeff Atwood
quelle
22
Beachten Sie, dass Sie einen IEqualityComparer als Parameter verwenden können, .Distinct(StringComparer.OrdinalIgnoreCase)um beispielsweise einen eindeutigen Satz von Zeichenfolgen ohne Berücksichtigung der Groß- und Kleinschreibung zu erhalten.
Justisb
Ehrt Distinct die ursprüngliche Reihenfolge der Elemente?
Asyrov
@asyrov: von MSDN:The Distinct() method returns an unordered sequence that contains no duplicate values.
Tigrou
52

Hier ist der HashSet <string> -Ansatz:

public static string[] RemoveDuplicates(string[] s)
{
    HashSet<string> set = new HashSet<string>(s);
    string[] result = new string[set.Count];
    set.CopyTo(result);
    return result;
}

Leider erfordert diese Lösung auch .NET Framework 3.5 oder höher, da HashSet erst in dieser Version hinzugefügt wurde. Sie können auch array.Distinct () verwenden , eine Funktion von LINQ.

Arcturus
quelle
11
Dadurch wird die ursprüngliche Bestellung wahrscheinlich nicht beibehalten.
Hamish Grubijan
11

Der folgende getestete und funktionierende Code entfernt Duplikate aus einem Array. Sie müssen den System.Collections-Namespace einschließen.

string[] sArray = {"a", "b", "b", "c", "c", "d", "e", "f", "f"};
var sList = new ArrayList();

for (int i = 0; i < sArray.Length; i++) {
    if (sList.Contains(sArray[i]) == false) {
        sList.Add(sArray[i]);
    }
}

var sNew = sList.ToArray();

for (int i = 0; i < sNew.Length; i++) {
    Console.Write(sNew[i]);
}

Sie können dies in eine Funktion einbinden, wenn Sie möchten.

GateKiller
quelle
Dies scheint O (N ^ 2) zu sein ... Sie könnten einen Heap anstelle einer ArrayList verwenden
Neil Chowdhury
10

Wenn Sie es sortieren müssen, können Sie eine Sortierung implementieren, die auch Duplikate entfernt.

Tötet dann zwei Fliegen mit einer Klappe.

Matthew Schinckel
quelle
7
Wie werden beim Sortieren Duplikate entfernt?
Dan1
2
Wer hat das gewählt? Dies ist keine Antwort. "Wie mache ich Pfannkuchen?" "Geben Sie einige Zutaten in einen Bogen und mischen Sie."
Quarkly
9

Dies hängt möglicherweise davon ab, wie viel Sie für die Lösung benötigen. Wenn das Array niemals so groß wird und Sie die Liste nicht sortieren möchten, möchten Sie möglicherweise etwas Ähnliches wie das Folgende ausprobieren:

    public string[] RemoveDuplicates(string[] myList) {
        System.Collections.ArrayList newList = new System.Collections.ArrayList();

        foreach (string str in myList)
            if (!newList.Contains(str))
                newList.Add(str);
        return (string[])newList.ToArray(typeof(string));
    }
rjzii
quelle
4
Sie sollten List anstelle von ArrayList verwenden.
Doug S
7

- Dies ist die Interviewfrage , die jedes Mal gestellt wird. Jetzt habe ich seine Codierung gemacht.

static void Main(string[] args)
{    
            int[] array = new int[] { 4, 8, 4, 1, 1, 4, 8 };            
            int numDups = 0, prevIndex = 0;

            for (int i = 0; i < array.Length; i++)
            {
                bool foundDup = false;
                for (int j = 0; j < i; j++)
                {
                    if (array[i] == array[j])
                    {
                        foundDup = true;
                        numDups++; // Increment means Count for Duplicate found in array.
                        break;
                    }                    
                }

                if (foundDup == false)
                {
                    array[prevIndex] = array[i];
                    prevIndex++;
                }
            }

            // Just Duplicate records replce by zero.
            for (int k = 1; k <= numDups; k++)
            {               
                array[array.Length - k] = '\0';             
            }


            Console.WriteLine("Console program for Remove duplicates from array.");
            Console.Read();
        }
Muhammad Mubashir
quelle
3
Sie sollten für diese Frage keine O (n * 2) -Zeitkomplexität durchführen.
Dan1
2
Sie sollten Merge Sort verwenden
Nick Gallimore
7
List<String> myStringList = new List<string>();
foreach (string s in myStringArray)
{
    if (!myStringList.Contains(s))
    {
        myStringList.Add(s);
    }
}

Dies ist O (n ^ 2) , was für eine kurze Liste, die in eine Combo gestopft wird, keine Rolle spielt, aber bei einer großen Sammlung schnell ein Problem sein könnte.

Will Dean
quelle
6
protected void Page_Load(object sender, EventArgs e)
{
    string a = "a;b;c;d;e;v";
    string[] b = a.Split(';');
    string[] c = b.Distinct().ToArray();

    if (b.Length != c.Length)
    {
        for (int i = 0; i < b.Length; i++)
        {
            try
            {
                if (b[i].ToString() != c[i].ToString())
                {
                    Response.Write("Found duplicate " + b[i].ToString());
                    return;
                }
            }
            catch (Exception ex)
            {
                Response.Write("Found duplicate " + b[i].ToString());
                return;
            }
        }              
    }
    else
    {
        Response.Write("No duplicate ");
    }
}
Pintu
quelle
6

Hier ist ein O (n * n) -Ansatz, der den O (1) -Raum verwendet.

void removeDuplicates(char* strIn)
{
    int numDups = 0, prevIndex = 0;
    if(NULL != strIn && *strIn != '\0')
    {
        int len = strlen(strIn);
        for(int i = 0; i < len; i++)
        {
            bool foundDup = false;
            for(int j = 0; j < i; j++)
            {
                if(strIn[j] == strIn[i])
                {
                    foundDup = true;
                    numDups++;
                    break;
                }
            }

            if(foundDup == false)
            {
                strIn[prevIndex] = strIn[i];
                prevIndex++;
            }
        }

        strIn[len-numDups] = '\0';
    }
}

Die oben genannten Hash / Linq- Ansätze werden im Allgemeinen im wirklichen Leben verwendet. In Interviews möchten sie jedoch normalerweise einige Einschränkungen festlegen, z. B. konstanten Speicherplatz, der Hash oder keine interne API ausschließt - was die Verwendung von LINQ ausschließt .

Sesh
quelle
1
Wie kann es jemals O (1) Speicherplatz verwenden, wenn Sie die gesamte Liste speichern müssen? Wenn Sie mit einer Inplace-Sortierung beginnen, können Sie O (nlogn) -Zeit und O (n) -Speicher mit viel weniger Code ausführen.
Thomas Ahle
1
Was lässt Sie denken, dass die gesamte Liste gespeichert wird? Es ist in der Tat an Ort und Stelle. Und obwohl dies keine Bedingung in der Frage ist, behält mein Code die Reihenfolge der Zeichen in der ursprünglichen Zeichenfolge bei. Durch Sortieren wird das entfernt.
Sesh
1
Die innere Schleife ( strIn[j] == strIn[i]) vergleicht eine Zeichenfolge mit sich selbst, sofern dies nicht mit einer if-Anweisung berücksichtigt wird.
User3219
5

Fügen Sie alle Zeichenfolgen zu einem Wörterbuch hinzu und rufen Sie anschließend die Keys-Eigenschaft ab. Dadurch wird jede eindeutige Zeichenfolge erzeugt, jedoch nicht unbedingt in derselben Reihenfolge, in der Ihre ursprüngliche Eingabe sie hatte.

Wenn das Endergebnis dieselbe Reihenfolge wie die ursprüngliche Eingabe haben soll, verwenden Sie stattdessen den folgenden Algorithmus, wenn Sie das erste Vorkommen jeder Zeichenfolge berücksichtigen:

  1. Haben Sie eine Liste (endgültige Ausgabe) und ein Wörterbuch (um nach Duplikaten zu suchen)
  2. Überprüfen Sie für jede Zeichenfolge in der Eingabe, ob sie bereits im Wörterbuch vorhanden ist
  3. Wenn nicht, fügen Sie es sowohl dem Wörterbuch als auch der Liste hinzu

Am Ende enthält die Liste das erste Vorkommen jeder einzelnen Zeichenfolge.

Stellen Sie sicher, dass Sie beim Erstellen Ihres Wörterbuchs Dinge wie Kultur und dergleichen berücksichtigen, um sicherzustellen, dass Sie Duplikate mit Buchstaben mit Akzent korrekt behandeln.

Lasse V. Karlsen
quelle
5

Der folgende Code versucht, Duplikate aus einer ArrayList zu entfernen, obwohl dies keine optimale Lösung ist. Diese Frage wurde mir während eines Interviews gestellt, um Duplikate durch Rekursion und ohne Verwendung einer zweiten / temporären Arrayliste zu entfernen:

private void RemoveDuplicate() 
{

ArrayList dataArray = new ArrayList(5);

            dataArray.Add("1");
            dataArray.Add("1");
            dataArray.Add("6");
            dataArray.Add("6");
            dataArray.Add("6");
            dataArray.Add("3");
            dataArray.Add("6");
            dataArray.Add("4");
            dataArray.Add("5");
            dataArray.Add("4");
            dataArray.Add("1");

            dataArray.Sort();

            GetDistinctArrayList(dataArray, 0);
}

private void GetDistinctArrayList(ArrayList arr, int idx)

{

            int count = 0;

            if (idx >= arr.Count) return;

            string val = arr[idx].ToString();
            foreach (String s in arr)
            {
                if (s.Equals(arr[idx]))
                {
                    count++;
                }
            }

            if (count > 1)
            {
                arr.Remove(val);
                GetDistinctArrayList(arr, idx);
            }
            else
            {
                idx += 1;
                GetDistinctArrayList(arr, idx);
            }
        }
Vijay Swami
quelle
5

Einfache Lösung:

using System.Linq;
...

public static int[] Distinct(int[] handles)
{
    return handles.ToList().Distinct().ToArray();
}
Fábio Delboni
quelle
5

Möglicherweise Hashset, das keine doppelten Elemente speichert und Anforderungen zum Hinzufügen von Duplikaten stillschweigend ignoriert.

static void Main()
{
    string textWithDuplicates = "aaabbcccggg";     

    Console.WriteLine(textWithDuplicates.Count());  
    var letters = new HashSet<char>(textWithDuplicates);
    Console.WriteLine(letters.Count());

    foreach (char c in letters) Console.Write(c);
    Console.WriteLine("");

    int[] array = new int[] { 12, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2 };

    Console.WriteLine(array.Count());
    var distinctArray = new HashSet<int>(array);
    Console.WriteLine(distinctArray.Count());

    foreach (int i in distinctArray) Console.Write(i + ",");
}
lukaszk
quelle
4

HINWEIS: NICHT getestet!

string[] test(string[] myStringArray)
{
    List<String> myStringList = new List<string>();
    foreach (string s in myStringArray)
    {
        if (!myStringList.Contains(s))
        {
            myStringList.Add(s);
        }
    }
    return myStringList.ToString();
}

Könnte tun, was Sie brauchen ...

EDIT Argh !!! von Rob in weniger als einer Minute geschlagen!

ZombieSheep
quelle
Rob hat dich zu nichts geschlagen. Er verwendet ArrayList, während Sie List verwenden. Ihre Version ist besser.
Doug S
4

Testete das unten und es funktioniert. Was cool ist, ist, dass es auch eine kultursensible Suche durchführt

class RemoveDuplicatesInString
{
    public static String RemoveDups(String origString)
    {
        String outString = null;
        int readIndex = 0;
        CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;


        if(String.IsNullOrEmpty(origString))
        {
            return outString;
        }

        foreach (var ch in origString)
        {
            if (readIndex == 0)
            {
                outString = String.Concat(ch);
                readIndex++;
                continue;
            }

            if (ci.IndexOf(origString, ch.ToString().ToLower(), 0, readIndex) == -1)
            {
                //Unique char as this char wasn't found earlier.
                outString = String.Concat(outString, ch);                   
            }

            readIndex++;

        }


        return outString;
    }


    static void Main(string[] args)
    {
        String inputString = "aAbcefc";
        String outputString;

        outputString = RemoveDups(inputString);

        Console.WriteLine(outputString);
    }

}}

--AptSenSDET

AptSenSDET
quelle
4

Dieser Code entfernt zu 100% doppelte Werte aus einem Array [wie ich ein [i] verwendet habe] ..... Sie können es in jede OO-Sprache konvertieren ..... :)

for(int i=0;i<size;i++)
{
    for(int j=i+1;j<size;j++)
    {
        if(a[i] == a[j])
        {
            for(int k=j;k<size;k++)
            {
                 a[k]=a[k+1];
            }
            j--;
            size--;
        }
    }

}
Salman Ramzan
quelle
4

Generische Erweiterungsmethode:

public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
{
    if (source == null)
        throw new ArgumentNullException(nameof(source));

    HashSet<TSource> set = new HashSet<TSource>(comparer);
    foreach (TSource item in source)
    {
        if (set.Add(item))
        {
            yield return item;
        }
    }
}
Ali Bayat
quelle
1

Sie können diesen Code verwenden, wenn Sie mit einer ArrayList arbeiten

ArrayList arrayList;
//Add some Members :)
arrayList.Add("ali");
arrayList.Add("hadi");
arrayList.Add("ali");

//Remove duplicates from array
  for (int i = 0; i < arrayList.Count; i++)
    {
       for (int j = i + 1; j < arrayList.Count ; j++)
           if (arrayList[i].ToString() == arrayList[j].ToString())
                 arrayList.Remove(arrayList[j]);
reza akhlaghi
quelle
1
public static int RemoveDuplicates(ref int[] array)
{
    int size = array.Length;

    // if 0 or 1, return 0 or 1:
    if (size  < 2) {
        return size;
    }

    int current = 0;
    for (int candidate = 1; candidate < size; ++candidate) {
        if (array[current] != array[candidate]) {
            array[++current] = array[candidate];
        }
    }

    // index to count conversion:
    return ++current;
}
Harry Martyrossian
quelle
0

Im Folgenden finden Sie eine einfache Logik in Java, mit der Sie Elemente eines Arrays zweimal durchlaufen. Wenn Sie dasselbe Element sehen, weisen Sie ihm Null zu und berühren den Index des zu vergleichenden Elements nicht.

import java.util.*;
class removeDuplicate{
int [] y ;

public removeDuplicate(int[] array){
    y=array;

    for(int b=0;b<y.length;b++){
        int temp = y[b];
        for(int v=0;v<y.length;v++){
            if( b!=v && temp==y[v]){
                y[v]=0;
            }
        }
    }
}
Papasani Mohansrinivas
quelle
0
  private static string[] distinct(string[] inputArray)
        {
            bool alreadyExists;
            string[] outputArray = new string[] {};

            for (int i = 0; i < inputArray.Length; i++)
            {
                alreadyExists = false;
                for (int j = 0; j < outputArray.Length; j++)
                {
                    if (inputArray[i] == outputArray[j])
                        alreadyExists = true;
                }
                        if (alreadyExists==false)
                        {
                            Array.Resize<string>(ref outputArray, outputArray.Length + 1);
                            outputArray[outputArray.Length-1] = inputArray[i];
                        }
            }
            return outputArray;
        }
Arie Yehieli
quelle
1
Erklären Sie bitte Ihre Antwort.
Badiparmagi
0
using System;
using System.Collections.Generic;
using System.Linq;


namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
             List<int> listofint1 = new List<int> { 4, 8, 4, 1, 1, 4, 8 };
           List<int> updatedlist= removeduplicate(listofint1);
            foreach(int num in updatedlist)
               Console.WriteLine(num);
        }


        public static List<int> removeduplicate(List<int> listofint)
         {
             List<int> listofintwithoutduplicate= new List<int>();


              foreach(var num in listofint)
                 {
                  if(!listofintwithoutduplicate.Any(p=>p==num))
                        {
                          listofintwithoutduplicate.Add(num);
                        }
                  }
             return listofintwithoutduplicate;
         }
    }



}
Rohan
quelle
Dies ist eine sehr ineffiziente Methode. Schauen Sie sich die anderen Antworten an, um zu sehen, was sie tun.
Wai Ha Lee
0
strINvalues = "1,1,2,2,3,3,4,4";
strINvalues = string.Join(",", strINvalues .Split(',').Distinct().ToArray());
Debug.Writeline(strINvalues);

Kkk Ich bin mir nicht sicher, ob dies Hexerei oder nur schöner Code ist

1 strINvalues ​​.Split (','). Distinct (). ToArray ()

2 string.Join (",", XXX);

1 Teilen Sie das Array und entfernen Sie Duplikate mit Distinct [LINQ]. 2 Fügen Sie es ohne Duplikate wieder zusammen.

Entschuldigung, ich habe nie den Text auf StackOverFlow gelesen, nur den Code. es macht mehr Sinn als der Text;)

Kudakwashe Mafutah
quelle
Nur-Code-Antworten sind Antworten von geringer Qualität. Fügen Sie eine Erklärung hinzu, warum dies funktioniert.
Taslim Oseni
0
int size = a.Length;
        for (int i = 0; i < size; i++)
        {
            for (int j = i + 1; j < size; j++)
            {
                if (a[i] == a[j])
                {
                    for (int k = j; k < size; k++)
                    {
                        if (k != size - 1)
                        {
                            int temp = a[k];
                            a[k] = a[k + 1];
                            a[k + 1] = temp;

                        }
                    }
                    j--;
                    size--;
                }
            }
        }
Swathi Sriramaneni
quelle
1
Willkommen bei SO. Während dieses Code-Snippet die Lösung sein kann, hilft das Hinzufügen einer Erklärung wirklich, die Qualität Ihres Beitrags zu verbessern. Denken Sie daran, dass Sie die Frage für Leser in Zukunft beantworten und diese Personen möglicherweise die Gründe für Ihren Codevorschlag nicht kennen.
alan.elkin
Leider entfernt dieser Code nichts, sodass keine Duplikate entfernt werden.
P_P
0

Die beste Art? Schwer zu sagen, der HashSet-Ansatz sieht schnell aus, aber (abhängig von den Daten) die Verwendung eines Sortieralgorithmus (CountSort?) Kann viel schneller sein.

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main()
    {
        Random r = new Random(0); int[] a, b = new int[1000000];
        for (int i = b.Length - 1; i >= 0; i--) b[i] = r.Next(b.Length);
        a = new int[b.Length]; Array.Copy(b, a, b.Length);
        a = dedup0(a); Console.WriteLine(a.Length);
        a = new int[b.Length]; Array.Copy(b, a, b.Length);
        var w = System.Diagnostics.Stopwatch.StartNew();
        a = dedup0(a); Console.WriteLine(w.Elapsed); Console.Read();
    }

    static int[] dedup0(int[] a)  // 48 ms  
    {
        return new HashSet<int>(a).ToArray();
    }

    static int[] dedup1(int[] a)  // 68 ms
    {
        Array.Sort(a); int i = 0, j = 1, k = a.Length; if (k < 2) return a;
        while (j < k) if (a[i] == a[j]) j++; else a[++i] = a[j++];
        Array.Resize(ref a, i + 1); return a;
    }

    static int[] dedup2(int[] a)  //  8 ms
    {
        var b = new byte[a.Length]; int c = 0;
        for (int i = 0; i < a.Length; i++) 
            if (b[a[i]] == 0) { b[a[i]] = 1; c++; }
        a = new int[c];
        for (int j = 0, i = 0; i < b.Length; i++) if (b[i] > 0) a[j++] = i;
        return a;
    }
}

Fast verzweigungsfrei. Wie? Debug-Modus, Schritt in (F11) mit einem kleinen Array: {1,3,1,1,0}

    static int[] dedupf(int[] a)  //  4 ms
    {
        if (a.Length < 2) return a;
        var b = new byte[a.Length]; int c = 0, bi, ai, i, j;
        for (i = 0; i < a.Length; i++)
        { ai = a[i]; bi = 1 ^ b[ai]; b[ai] |= (byte)bi; c += bi; }
        a = new int[c]; i = 0; while (b[i] == 0) i++; a[0] = i++;
        for (j = 0; i < b.Length; i++) a[j += bi = b[i]] += bi * i; return a;
    }

Eine Lösung mit zwei verschachtelten Schleifen kann einige Zeit in Anspruch nehmen, insbesondere bei größeren Arrays.

    static int[] dedup(int[] a)
    {
        int i, j, k = a.Length - 1;
        for (i = 0; i < k; i++)
            for (j = i + 1; j <= k; j++) if (a[i] == a[j]) a[j--] = a[k--];
        Array.Resize(ref a, k + 1); return a;
    }
P_P
quelle