在 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 上找到本文的完整代碼示例。