Frage Wie finde ich ein Vielfaches der gleichen Integer in einer Arraylist?


Mein Problem ist wie folgt. Ich habe eine Arraylist von ganzen Zahlen. Die Arraylist enthält 5 Intez. Z.B. [5,5,3,3,9] oder vielleicht [2,2,2,2,7]. Viele der Arraylisten haben doppelte Werte und ich bin mir nicht sicher, wie man zählt, wie viele von jedem der Werte existieren.

Das Problem ist, wie man die doppelten Werte in der Arraylist findet und zählt, wie viele von diesem bestimmten Duplikat es gibt. Im ersten Beispiel [5,5,3,3,9] gibt es 2 5 und 2 3. Das zweite Beispiel von [2,2,2,2,7] wäre nur 4 2. Die resultierende Information, die ich finden möchte, ist, ob es Dubletten gibt, wie viele davon vorhanden sind und welche spezifische Integer dupliziert wurde.

Ich bin mir nicht sicher, wie man das in Java macht.

Jede Hilfe würde sehr geschätzt werden. Vielen Dank.


5
2018-04-29 22:38


Ursprung


Antworten:


Die einfachste Antwort wäre für mich die Verwendung der Collections.frequency Methode. Etwas in der Art von:

// Example ArrayList with Integer values
ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(2);
intList.add(2);
intList.add(2);
intList.add(2);
intList.add(7);

Set<Integer> noDupes = new HashSet<Integer>();
noDupes.addAll(intList); // Remove duplicates

for (Integer i : noDupes) {
    int occurrences = Collections.frequency(intList, i);
    System.out.println(i + " occurs " + occurrences + " times.");
}

Wenn Sie möchten, können Sie jeden zuordnen Integer mit seiner Anzahl von Vorkommen:

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer i : noDupes) {
    map.put(i, Collections.frequency(intList, i));
}

6
2018-04-30 00:34



Zwei Algorithmen fallen mir ein.

Ordne es (Collections.sort). Dann iterieren Sie einfach und finden Sie die Duplikate.

Iterate durch Zählung in a Map<Integer,Integer> (oder Map<Integer,AtomicInteger> für eine veränderbare Zählung). Ein bisschen hässlich auf diese Weise.

In jedem Fall sollte das Programmieren eine lehrreiche Übung sein. Ich schlage vor, beides zu tun und zu vergleichen.


5
2018-04-29 22:39



Hier ist eine konkrete Implementierung, mit Test, was ich in Kommentaren zu @ Toms Antwort beschrieben habe:

package playground.tests;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

import junit.framework.TestCase;

public class DupeCounterTest extends TestCase {

    public void testCountDupes() throws Exception {
        int[] array = new int[] { 5, 5, 3, 3, 9 };
        assertEquals("{3=2, 5=2}", countDupes(array).toString());
    }

    private Map<Integer, AtomicInteger> countDupes(int[] array) {
        Map<Integer, AtomicInteger> map = new HashMap<Integer, AtomicInteger>();
        // first create an entry in the map for every value in the array
        for (int i : array)
            map.put(i, new AtomicInteger());
        // now count all occurrences
        for (int i : array)
            map.get(i).addAndGet(1);
        // now get rid of those where no duplicate exists
        HashSet<Integer> discards = new HashSet<Integer>();
        for (Integer i : map.keySet())
            if (map.get(i).get() == 1)
                discards.add(i);
        for (Integer i : discards) 
            map.remove(i);
        return map;
    }

}

3
2018-04-29 23:10



Verwenden Sie zusätzlich zur Array-Liste eine Hashmap-Auflistung

  • Der Hashmap-Schlüssel ist der eindeutige Array-Int-Wert und
  • Der Hashmap-Wert für den Schlüssel ist die Anzahl der gefundenen Werte.

Verfolgen Sie Ihre Array-Liste, indem Sie diese Werte in die Hash-Map aufnehmen. Fügen Sie ein neues Element hinzu, wenn kein vorheriger Schlüssel vorhanden ist, und erhöhen Sie die Werte der bereits vorhandenen Schlüssel um 1. Dann iteriere über die Hashmap und drucke alle Schlüssel aus, deren Wert> 1 ist.


1
2018-04-29 22:41



Du kannst durch die List und leg sie in eine Map mit der Zählung. Dann ist es einfach herauszufinden, welcher dupliziert ist.


1
2018-04-29 22:44



Für eine sauberere Abstraktion von dem, was Sie tun, könnten Sie das verwenden Multiset Datenstruktur von Guave/Google-Sammlungen. Vielleicht finden Sie sogar, dass Sie es lieber verwenden als ein List, je nachdem, was Sie damit machen (wenn Sie die deterministische Anordnung einer Liste nicht benötigen). Du würdest es so benutzen:

Multiset<Integer> multiset = HashMultiset.create(list);
int count = multiset.count(3); // gets the number of 3s that were in the list

In Bezug auf das, was das oben genannte unter den Deckeln tut, entspricht es fast genau dem Vorschlag, ein Gebäude zu bauen Map<Integer,AtomicInteger> basierend auf Ihrer Liste.


0
2018-04-29 23:01