在 Java 中查找列表中的所有重複項

一、簡介

在本文中，我們將學習在 Java List中查找重複項的不同方法。

給定一個包含重複元素的整數列表，我們將在其中找到重複元素。例如，給定輸入列表[1, 2, 3, 3, 4, 4, 5],輸出List將為[3, 4] 。

2. 使用Collection查找重複項

在本節中，我們將討論使用Collections提取列表中存在的重複元素的兩種方法。

2.1.使用Set的ontains()方法

Java 中的Set不包含重複項。 Set中的contains()方法僅當元素已存在於其中時才返回true 。

如果contains()返回false我們將向Set添加元素。否則，我們會將元素添加到輸出列表中。因此，輸出列表包含重複元素：

List<Integer> listDuplicateUsingSet(List<Integer> list) {
 List<Integer> duplicates = new ArrayList<>();
 Set<Integer> set = new HashSet<>();
 for (Integer i : list) {
 if (set.contains(i)) {
 duplicates.add(i);
 } else {
 set.add(i);
 }
 }
 return duplicates;
 }

讓我們編寫一個測試來檢查列表duplicates是否僅包含重複元素：

@Test
 void givenList_whenUsingSet_thenReturnDuplicateElements() {
 List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
 List<Integer> duplicates = listDuplicate.listDuplicateUsingSet(list);
 Assert.assertEquals(duplicates.size(), 2);
 Assert.assertEquals(duplicates.contains(3), true);
 Assert.assertEquals(duplicates.contains(4), true);
 Assert.assertEquals(duplicates.contains(1), false);
 }

這裡我們看到輸出列表只包含兩個元素3和4 。

這種方法對列表中的 n 個元素花費 O(n) 時間，對集合佔用大小為 n 的額外空間。

2.2.使用Map並存儲元素的頻率

我們可以使用Map來存儲每個元素的頻率，然後僅當元素的頻率不為1時才將它們添加到輸出列表：

List<Integer> listDuplicateUsingMap(List<Integer> list) {
 List<Integer> duplicates = new ArrayList<>();
 Map<Integer, Integer> frequencyMap = new HashMap<>();
 for (Integer number : list) {
 frequencyMap.put(number, frequencyMap.getOrDefault(number, 0) + 1);
 }
 for (int number : frequencyMap.keySet()) {
 if (frequencyMap.get(number) != 1) {
 duplicates.add(number);
 }
 }
 return duplicates;
 }

讓我們編寫一個測試來檢查列表重複項是否僅包含重複元素：

@Test
 void givenList_whenUsingFrequencyMap_thenReturnDuplicateElements() {
 List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
 List<Integer> duplicates = listDuplicate.listDuplicateUsingMap(list);
 Assert.assertEquals(duplicates.size(), 2);
 Assert.assertEquals(duplicates.contains(3), true);
 Assert.assertEquals(duplicates.contains(4), true);
 Assert.assertEquals(duplicates.contains(1), false);
 }

這裡我們看到輸出列表只包含兩個元素， 3和4 。

這種方法對列表中的 n 個元素花費 O(n) 時間，對映射佔用大小為 n 的額外空間。

3. 在 Java 8 中使用Stream

在本節中，我們將討論使用Stream提取列表中存在的重複元素的三種方法。

3.1.使用filter()和Set.add()方法

Set.add()將指定的元素添加到此集合中（如果它不存在）。如果此集合已包含該元素，則調用保持集合不變並返回false 。

在這裡，我們將使用Set並將列表轉換為流。將stream添加到Set,將重複的元素過濾收集到List:

List<Integer> listDuplicateUsingFilterAndSetAdd(List<Integer> list) {
 Set<Integer> elements = new HashSet<Integer>();
 return list.stream()
 .filter(n -> !elements.add(n))
 .collect(Collectors.toList());
 }

讓我們編寫一個測試來檢查列表重複項是否僅包含重複元素：

@Test
 void givenList_whenUsingFilterAndSetAdd_thenReturnDuplicateElements() {
 List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
 List<Integer> duplicates = listDuplicate.listDuplicateUsingFilterAndSetAdd(list);
 Assert.assertEquals(duplicates.size(), 2);
 Assert.assertEquals(duplicates.contains(3), true);
 Assert.assertEquals(duplicates.contains(4), true);
 Assert.assertEquals(duplicates.contains(1), false);
 }

在這裡，我們看到輸出元素僅包含兩個元素，如預期的那樣， 3和4 。

這種將filter()與Set.add()結合使用的方法是查找具有 O(n) 時間複雜度和集合大小為 n 的額外空間的重複元素的最快算法。

3.2.使用Collections.frequency()

Collections.frequency()返回指定集合中元素的數量，該數量等於指定值。在這裡，我們將List轉換為Stream並僅從Collections.frequency()中過濾掉返回值大於 1 的元素。

我們會將這些元素收集到Set中以避免重複，最後將Set轉換為List ：

List<Integer> listDuplicateUsingCollectionsFrequency(List<Integer> list) {
 List<Integer> duplicates = new ArrayList<>();
 Set<Integer> set = list.stream()
 .filter(i -> Collections.frequency(list, i) > 1)
 .collect(Collectors.toSet());
 duplicates.addAll(set);
 return duplicates;
 }

讓我們編寫一個測試來檢查重複項是否僅包含重複元素：

@Test
 void givenList_whenUsingCollectionsFrequency_thenReturnDuplicateElements() {
 List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
 List<Integer> duplicates = listDuplicate.listDuplicateUsingCollectionsFrequency(list);
 Assert.assertEquals(duplicates.size(), 2);
 Assert.assertEquals(duplicates.contains(3), true);
 Assert.assertEquals(duplicates.contains(4), true);
 Assert.assertEquals(duplicates.contains(1), false);
 }

正如預期的那樣，輸出列表僅包含兩個元素，3 和 4。

這種使用Collections.frequency()的方法是最慢的，因為它將每個元素與一個列表進行比較Collections.frequency(list, i) ，其複雜度為 O(n)。所以整體複雜度為 O(n*n)。它還需要一個大小為 n 的額外空間用於集合。

3.3.使用Map和Collectors.groupingBy()

Collectors.groupingBy()返回一個收集器，該收集器對輸入元素實施級聯“分組依據”操作。

它根據分類函數對元素進行分組，然後使用指定的下游收集器對具有給定鍵的關聯值執行歸約操作。分類函數將元素映射到某個鍵類型K 。下游收集器對輸入元素進行操作並產生D類型的結果。生成的收集器生成一個Map<K, D> 。

在這裡，我們將使用Function.identity()作為分類函數，使用Collectors.counting()作為下游收集器。

Function.identity()返回一個始終返回其輸入參數的函數。 Collectors.counting()返回一個接受元素的收集器，該元素計算輸入元素的數量。如果不存在任何元素，則結果為零。因此，我們將使用Collectors.groupingBy()獲得元素及其頻率的映射。

然後我們將這個Map的EntrySet轉成一個Stream ，只過濾掉大於1的元素，收集到一個Set中，避免重複。然後將Set轉換為List:

List<Integer> listDuplicateUsingMapAndCollectorsGroupingBy(List<Integer> list) {
 List<Integer> duplicates = new ArrayList<>();
 Set<Integer> set = list.stream()
 .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
 .entrySet()
 .stream()
 .filter(m -> m.getValue() > 1)
 .map(Map.Entry::getKey)
 .collect(Collectors.toSet());
 duplicates.addAll(set);
 return duplicates;
 }

讓我們編寫一個測試來檢查列表duplicates是否僅包含重複元素：

@Test
 void givenList_whenUsingMapAndCollectorsGroupingBy_thenReturnDuplicateElements() {
 List<Integer> list = Arrays.asList(1, 2, 3, 3, 4, 4, 5);
 List<Integer> duplicates = listDuplicate.listDuplicateUsingCollectionsFrequency(list);
 Assert.assertEquals(duplicates.size(), 2);
 Assert.assertEquals(duplicates.contains(3), true);
 Assert.assertEquals(duplicates.contains(4), true);
 Assert.assertEquals(duplicates.contains(1), false);
 }

這裡我們看到輸出元素只包含兩個元素3和4 。

Collectors.groupingBy()需要 O(n) 時間。對生成的 EntrySet 執行filter()操作EntrySet,但複雜度仍然為 O(n)，因為地圖查找時間為 O(1)。它還需要一個額外的空間 n 用於集合。

4。結論

在本文中，我們了解了在 Java 中從List中提取重複元素的不同方法。

我們討論了使用Set和Map方法及其使用Stream相應方法。使用Stream代碼更具聲明性，並且無需外部迭代器即可清楚地傳達代碼的意圖。

與往常一樣，可以在 GitHub 上找到本文的完整代碼示例。