Wiederholte Zahlen in einem Array suchen

128080
Hatori Sanso

Ich möchte ein Array von n Zahlen durchsuchen und die Nummern finden, die wiederholt werden. Bisher habe ich diesen Code, der die Aufgabe erfüllt, aber ich finde, dass dies eine ziemlich umständliche Methode ist, aber ich finde keine andere Methode dafür.

class Checknumber{
    int [] numbers = new int [5];
    Scanner inn = new Scanner(System.in);
    boolean b = true;
    int temp = -1;

    void sjekk(){
        System.out.println("Write five numbers");
        for(int i = 0; i < numbers.length; i++){
        numbers [i] = inn.nextInt();
    }

    //sjekker om det er like tall i arrayen
    System.out.print("\nNumbers that are repeated: ");
    for(int i = 0; i < numbers.length; i++){

        if(!b){
            System.out.print(temp + " ");
        }

        b = true;
        temp = numbers[i];
        for(int j = 0; j < numbers.length; j++){
            if(i != j && temp == numbers[j] && numbers[j] != -2){
                b = false;
                numbers[j] = -2;
            }
        }
    }

}
Antworten
17
Sie sollten die von Ihnen verwendete Sprache mit einem Tag versehen. vor 7 Jahren 0
Meinen Sie doppelte Zahlen oder eine Reihe identischer Zahlen in einer Serie? Sollte das die letzte "1" in "1231" oder die "3" in "12333333456" beseitigen? vor 7 Jahren 0
Eine andere Möglichkeit besteht darin, das Array zuerst zu sortieren, zum Beispiel mit [`Arrays.sort ()`] (http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort% 28int% 5B% 5D% 29). Dadurch würden sich wiederholte Zahlen nebeneinander befinden, wodurch die zum Finden und Drucken benötigte Logik vereinfacht wird. vor 7 Jahren 1
Ich hätte klarer sein sollen. Wenn ich "1 2 3 2 1" eingestellt habe, soll das Programm ausgedruckt werden: "Diese Zahlen wiederholen sich: 1 und 2" Hatori Sanso vor 7 Jahren 0
Bitte, alle hier, verwenden Sie für-jede; Dies ist 2013 und nicht 2003. for (int i: numbers) {} Bitte beseitigen Sie eine triviale Fehlerquelle. itsbruce vor 7 Jahren 0
Wenn Sie mit einer Big-Data-Situation konfrontiert sind, ist die Kardinalitätsschätzung (http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation) eine probabilistische Methode, um herauszufinden, wie viele eindeutige (oder wiederholte) ) Elemente befinden sich in einem Datensatz. Pat vor 6 Jahren 0

7 Antworten auf die Frage

13
200_success

Others have given alternate solutions. However, since this is Code Review, I'll offer a critique instead, because I think you will learn more from that than by just seeing the answer.

Interfaces

  • Checknumber is too vague. I suggest DuplicateNumberDetector.
  • In your interfaces (class and method names), pick either English or Norwegian and stick with it. For your comments, use whatever language works for you.
  • sjekk() (meaning "check") is actually responsible for receiving input rather than performing the checking. How misleading!

Variables

  • b is very poorly named. I suggest unique instead.
  • temp is somewhat poorly named. I suggest num instead.
  • Only older dialects of C require you to declare all variables at the top. Java lets you declare variables near the point of first use. You should take advantage of that. int temp should be declared inside the for (i) loop, since it is never used outside the loop.
  • You might try to pull the declaration of b inside the for (i) loop too. But then you will realize that b refers to the uniqueness of the previous numbers[i]. That reveals a bug: what if the last two numbers are identical (numbers[3] == numbers[4], but numbers[2] != numbers[3])? You haven't handled the termination case correctly. Hint: Move your print statement. The lesson to be learned here is that declaring temporary variables far from the point of use is almost as evil and dangerous as using global variables.

Logic

  • You are using -2 as a special value to indicate that an array element has already been detected as a duplicate. That's bad because your code will fail if -2 happens to be one of the inputs.
  • Overwriting the input array is a surprising side effect. That's as unforgivable as sending your computer to a repair shop to install a video card and getting it back with the hard drive reformatted. If you really need to overwrite the input, state so clearly in a comment. You should be able to find a solution to this problem that does not require overwriting.
  • Your inner loop has j going from 0 to the end of the array. That means you are handling every pair twice. You should probably be able to start from i + 1 instead, to reduce your processing in half. Handling each pair only once should simplify your logic as well.

Efficiency

  • You have two for loops, each iterating over the entire array. If the array has n elements, then the run time for your algorithm is O(n2). (Even with the inner-loop optimization mentioned in the previous point, it would still be O(n2).) For a small homework problem like this, that is perfectly acceptable, because simplicity is the main goal. If you wanted to handle very large arrays, though, it would be more efficient to sort the input first or use a HashMap.

Separation of concerns

  • Your input, processing, and output code are all intertwined. Get into the habit of separating them. Your code will be more reusable and easier to understand.

.

public class DuplicateNumberDetector {  
    int[] promptInputs(int numberOfInputs) { ... }

    // If the order doesn't matter, use Set<Integer> instead
    List<Integer> findDuplicates(int[] numbers) { ... }

    void printDuplicates(List<Integer> dups) { ... }

    public static void main(String[] args) {
        printDuplicates(findDuplicates(promptInputs(5)));
    }
}
12
Phil K
int[] numbers = { 1, 5, 23, 2, 1, 6, 3, 1, 8, 12, 3 };
Arrays.sort(numbers);

for(int i = 1; i < numbers.length; i++) {
    if(numbers[i] == numbers[i - 1]) {
        System.out.println("Duplicate: " + numbers[i]);
    }
}

Dadurch wird das Array numerisch sortiert und anschließend wird das Array durchlaufen. Es überprüft das vorherige Element im Array und wenn es dem aktuellen Element entspricht, haben Sie ein Duplikat.

Am besten lesbar. Ein kleiner Vorschlag: Fügen Sie hinter der if -Anweisung in der Schleife ein `while (i <numbers.length && numbers [i] == numbers [i - 1]) ++ ein, um Mehrfachausgabe zu verhindern (entsprechend dem ursprünglichen Verhalten). tb- vor 7 Jahren 4
Vielen Dank für Ihre Antwort! Ich bin sehr neu in der Programmierung, daher habe ich solche Funktionen noch nicht so gut gelernt, und jetzt sehe ich, dass es viel einfachere Wege gibt, dies zu tun. Ich habe diesen Code ausprobiert und er funktioniert. Wenn jedoch mehr als zwei ähnliche Zahlen im Array vorhanden sind, wird diese Zahl n-2-mal so oft wie die Anzahl der Wiederholungen im Array ausgegeben. Ich habe es nicht geschafft, den kleinen Vorschlag unten zu integrieren. Hatori Sanso vor 7 Jahren 1
Dies ist nicht das Optimum, aber schnell genug. Es sollte wahrscheinlich auch eine Überprüfung auf mehrere Duplikate erfolgen. Ich würde erwarten, dass [1, 1, 1, 2, 3] nur "Duplicate: 1" ausgibt. Dies ist einfach zu implementieren: `if (zahlen [i] == zahlen [i - 1] && zahlen [i]! = LastDup)`. beatgammit vor 7 Jahren 0
Sie haben das ursprüngliche Array geändert, das möglicherweise nicht gewünscht wurde. Das Erstellen einer sortierten Kopie wäre höflich. itsbruce vor 7 Jahren 0
Das größte Problem, das ich mit dieser Lösung habe, ist, dass sie nicht zu sehr n groß skaliert wird (da das gesamte Array auf einmal im Arbeitsspeicher gehalten werden muss). Aber es ist eine elegante Lösung für relativ kleine n (<1.000.000?). Graham vor 6 Jahren 0
6
Henrik Andersson

Ich werde auch meine 2 Cent einwerfen :)

Wenn Sie Objekte benutzen dürfen, würde ich das so machen.

Setzt automatisch Nicht-Duplikate ein. Wenn sie also enthalten ist, besteht keine Chance, dass der Wert erneut in einen Wert geht.

int[] arrayOfInt = { 1, 2, 3, 5, 1, 2, 7, 8, 9, 10 };
Set<Integer> notDupes = new HashSet<Integer>();
Set<Integer> duplicates = new HashSet<Integer>();
for (int i = 0; i < arrayOfInt.length; i++) {
    if (!notDupes.contains(arrayOfInt[i])) {
        notDupes .add(arrayOfInt[i]);
        continue;
    }
    duplicates.add(arrayOfInt[i]);
}
System.out.println("num of dups:" + duplicates.size());
System.out.println("num of norls:" + notDupes.size());
+1, aber Sie wissen nicht, wie viele Duplikate Sie für eine Nummer haben. Verwenden Sie also `MapDuplikate; = .. `und` int nbDuplicat = (int) duplicates.get (xNumber) `und` duplicates.put (nbDuplicat == 0? 1: nbDuplicat ++) `- Sie können auch 'if (! notDupes .add (arrayOfInt [i ]);) { fortsetzen; } duplicates.add (arrayOfInt [i]); `Da es nicht hinzugefügt werden kann, gibt es 'false' zurück ,integer> cl-r vor 7 Jahren 1
Das war jedoch nicht unberührt. Henrik Andersson vor 7 Jahren 0
Sie haben Recht! aber meine Erfahrung im wahren Leben hat vermutet, dass es bald gefragt wird, cl-r vor 7 Jahren 1
5
SJuan76

Erstellen Sie ein Map<Integer, Integer>(die erste Zahl ist die Nummer, die Sie suchen, zweitens die Anzahl der Auftritte).

Führen Sie Ihr Array durch. Jedes Mal, map.get(numberFound)wenn Sie eine Nummer finden, überprüfen Sie, ob Sie sie bereits gefunden haben. Wenn dies nicht der Fall war, geben Sie die Zahl mit einem Zähler von 1 ein. Wenn Sie den Zähler hatten, rufen Sie den Zähler auf, erhöhen Sie ihn und legen Sie ihn zurück in die Karte.

3
Jagdeep Sidhu

Ich würde Setfür diese Logik verwenden:

  1. Erstellen Sie eine leere Set MySetund eine andere Set ResultSet.

  2. Lesen Sie jede Nummer und führen Sie diese darauf durch:

    1. Überprüfen Sie, ob es in ist MySet.
    2. Wenn es in ist MySet, dann legen Sie es ein ResultSet.
    3. Wenn es nicht in ist MySet, dann legen Sie es ein Myset.
  3. ResultSet enthält die erforderlichen Nummern.

Der Vorteil dieses Ansatzes ist, dass sich die Komplexität von O (n 2 ) auf O (nlog (n)) verringern würde .

Ich möchte lieber nur ein Set oder ein Array verwenden, da ich Programme erstellen möchte, die so wenig Speicher wie möglich benötigen, aber ich versuche das zum Spaß! Hatori Sanso vor 7 Jahren 1
Die Raumkomplexität ist immer noch N: D Jagdeep Sidhu vor 7 Jahren 0
@HatoriSanso "Ich würde lieber ein Set oder ein Array verwenden, um Programme zu erstellen, die so wenig Speicher wie möglich benötigen." Bitte seien Sie vorsichtig bei [Vorzeitige Optimierung] (http://en.wikipedia.org/wiki/Program_optimization) ! Es ist gut, dass Sie versuchen, effizient zu sein, aber erkennen, dass "effizient" in Bezug auf Computer viele Dinge bedeuten kann (Gedächtnis ist nur die Spitze des Eisbergs). Wenn Sie Zweifel haben: 1. Machen Sie es richtig 2. Machen Sie es richtig 3. Machen Sie es schnell (aka Optimieren) - [Kent Beck] (http://c2.com/cgi/wiki?MakeItWorkMakeItRightMakeItFast) Tony R vor 7 Jahren 1
Um nur meine 2 Cents hinzuzufügen, müssen Sie, wenn Sie optimieren möchten, immer die räumliche und zeitliche Komplexität berechnen, nicht nur die Anzahl der verwendeten Kopien. In meiner Lösung werden zwei Kopien für n Elemente (2n) verwendet, und in Ihrer Lösung wird eine Kopie verwendet (1n), die Platzkomplexität ist jedoch gleich N, daher ist es unwichtig. Es ist nur ein Problem, wenn Sie die Komplexität auf NlogN oder N ^ 2 erhöhen. Ihre Lösung hat auch eine zeitliche Komplexität von N ^ 2, und die von mir geschriebene Lösung hat den ungünstigsten Fall NlogN und ist daher effizienter. Zwei Datenkopien wirken sich nicht auf die Komplexität / Effizienz des Platzes aus. Jagdeep Sidhu vor 7 Jahren 0
3
Shilan

This is almost the easiest way! hashSet returns false whenever a duplicate number is added to it.

private static void findDuplicateNumber() {
    Set<Integer> hashSet = new HashSet<Integer>();

    for(int i=0; i < arr.length; i++){
        boolean unique = hashSet.add(arr[i]);
        if(unique == false)
            System.out.println("duplication " + arr[i]);
    }      

}
Sie sollten "if (! Unique) {...}" anstelle von "if (unique == false)" verwenden. Gute Entdeckung. rolfl vor 6 Jahren 1
"int [] arr" sollte ein Parameter für diese Funktion sein. (Sicher ist es kein statisches Mitglied der Klasse, richtig?) 200_success vor 6 Jahren 0
Besser wäre es, new-style für Loops zu verwenden: `for (int a: arr) {...}`. 200_success vor 6 Jahren 0
0
Subhrajyoti Majumder

Sie können das Google Collection Framework Guava verwenden Multiset<Integer>, um sich wiederholende Nummern zu finden.

Elemente eines Multisets, die einander gleich sind (siehe "Hinweis zur Elementäquivalenz" unten), werden als Vorkommen desselben einzelnen Elements bezeichnet. Die Gesamtzahl der Vorkommen eines Elements in einem Multiset wird als Anzahl dieses Elements bezeichnet (die Ausdrücke "Frequenz" und "Multiplizität" sind gleichwertig, werden aber in dieser API nicht verwendet). Da die Zählung eines Elements als int dargestellt wird, darf ein Multiset niemals mehr als ein Integer.MAX_VALUE-Vorkommen eines Elements enthalten.

Multiset<Integer> set = HashMultiset.create();
void sjekk(){
        System.out.println("Write five numbers");
        for(int i = 0; i < numbers.length; i++){
        set.add(inn.nextInt());
    }
...
for(Multiset.Entry<Integer> entry : set.entrySet()){ 
 System.out.println("Element :-> "+entry.getElement()+" Repeat Cnt :-> "+entry.getCount());
}