java 如何在java数组中查找重复项？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13658058/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find duplicates in a java array?
提问by user1859040
I'm trying to count how many duplicate items are in an array.
我正在尝试计算数组中有多少重复项。
Example:
例子：
[0, 2, 0] would return 2, [0, 0, 0] would return 3, [0, 1, 2] = 0
So far I have it working for when all three items are equal, but I'm not sure why it's returning one less than what it should for 2 items being the same.
到目前为止，当所有三个项目都相等时，我可以使用它，但我不确定为什么它返回的值比两个项目相同时返回的值少一个。
int equal = 0;
for(int i = 0; i < recent.length; i++) {
for(int j = i; j < recent.length; j++) {
if(i != j && recent[i].equals(recent[j])) {
equal++;
}
}
}
回答by Tomasz Nurkiewicz
Your algorithm is flawed in the following way: for every element in the array you look at all the elements after that element and if they happen to be equal, you increase the counter. However when you have 3 same elements, you count the last one twice - when you run internal loop for first and for second element. Moreover you never count the first element.
您的算法存在以下缺陷：对于数组中的每个元素，您查看该元素之后的所有元素，如果它们碰巧相等，则增加计数器。但是，当您有 3 个相同的元素时，您将最后一个计数两次 - 当您为第一个和第二个元素运行内部循环时。此外，您永远不会计算第一个元素。
So it works by accident for [0, 0, 0]but doesn't work for other inputs.
所以它偶然适用[0, 0, 0]于其他输入但不适用于其他输入。
回答by mbarrows
The code you gave counts equivalences, so it adds one every time an element equals another element.
您提供的代码计算等价，因此每次一个元素等于另一个元素时它都会添加一个。
It sounds like what you want is the number of duplicate items, which is the same as (length - number of items that don't have a duplicate). I will call the latter "uniqueItems".
听起来您想要的是重复项的数量，这与 (length - 没有重复项的项数) 相同。我将后者称为“uniqueItems”。
I would recommend the following:
我会推荐以下内容：
// set of every item seen
Set<Integer> allItems = new HashSet<Integer>();
// set of items that don't have a duplicate
Set<Integer> uniqueItems = new HashSet<Integer>();
for(int i = 0; i < recent.length; i++) {
Integer val = i;
if(allItems.contains(val)) {
// if we've seen the value before, it is not a "uniqueItem"
uniqueItems.remove(val);
} else {
// assume the value is a "uniqueItem" until we see it again
uniqueItems.add(val);
}
allItems.add(val);
}
return recent.length - uniqueItems.size();
回答by kelceyp
I think that having nested loops is quite inefficient. You should be able to do it in o(n) rather than o(n^2).
我认为嵌套循环效率很低。你应该能够在 o(n) 而不是 o(n^2) 中做到这一点。
If you time yours against the following...
如果您根据以下时间进行计时...
public void run() {
int[] array = createRandomArray(2000000, 1000000);
System.out.println(countNumDups1(array));
}
private int[] createRandomArray(int numElements, int maxNumExclusive) {
int[] array = new int[numElements];
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(maxNumExclusive);
}
return array;
}
private int countNumDups1(int[] array) {
Map<Integer, Integer> numToCountMap = new HashMap<>();
for (int i = 0; i < array.length; i++) {
Integer key = array[i];
if (numToCountMap.containsKey(key)) {
numToCountMap.put(key, numToCountMap.get(key) + 1);
}
else {
numToCountMap.put(key, 1);
}
}
int numDups = 0;
for (int i = 0; i < array.length; i++) {
Integer key = array[i];
if (numToCountMap.get(key) > 1) {
numDups++;
}
}
return numDups;
}
I think you'll find the above is much faster even considering the horrible inefficiency of autoboxing and object creation.
我认为即使考虑到自动装箱和对象创建的可怕低效率，您也会发现上述方法要快得多。
回答by user2418284
The below code works perfectly to find the duplicates
下面的代码可以完美地找到重复项
int array[] = {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};
HashMap<Integer,Integer> duplicates = new HashMap<Integer,Integer>();
for(int i=0; i<array.length; i++)
{
if(duplicates.containsKey(array[i]))
{
int numberOfOccurances = duplicates.get(array[i]);
duplicates.put(array[i], (numberOfOccurances + 1));
}else{
duplicates.put(array[i], 1);
}
}
Iterator<Integer> keys = duplicates.keySet().iterator();
System.out.print("Duplicates : " );
while(keys.hasNext())
{
int k = keys.next();
if(duplicates.get(k) > 1)
{
System.out.print(" "+k);
}
}
回答by raviteja katari
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class ArrayDuplicateCount {
/**
* @author:raviteja katari
*/
public static void main(String[] args) {
int intArray[] = {5, 1,4,4,4,5,1,2,1,2,5,5};
//for counting duplicate items
int c = 0;
//creating map collection to hold integers as keys and Cont as value
Map<Integer, Integer> nwmap = new LinkedHashMap<Integer, Integer>();
for (int i = 0; i <intArray.length; i++) {
//Assigning array element to key
Integer key = intArray[i];
//this code checks for elemnt if present updates count value else
//put the new Array elemnt into map and increment count
if(nwmap.containsKey(key)){
//updating key value by 1
nwmap.put(key, nwmap.get(key) + 1);
}else{
//Adding new array element to map and increasing count by 1
nwmap.put(key, c+1);
}
}
//printing map
System.out.println(nwmap);
}
}
output: {5=4, 1=3, 4=3, 2=2}
输出：{5=4, 1=3, 4=3, 2=2}
回答by Khan
public void TotalduplicateNumbers {
int a[] = {2,8,2,4,4,6,7,6,8,4,5};
Map<Integer,Integer> m = new HashMap<Integer,Integer>();
for(int i=0;i<a.length;i++){
if(!m.containsKey(a[i]))
{
m.put(a[i], 1);
}
else
{
m.put(a[i], (m.get(a[i])+1));
}
}
for(Integer i:m.keySet()){
System.out.println("Number "+i+" "+"Occours "+m.get(i)+" time,");
}
}
We have an array containing 11 numbers, The logic is to create a map using these no. in which KEYS of map would be the actual number that must be entered by user and no. of occournce of that actual no. would be the value of that KEY. Here, containsKey() method checks whether the map contain that key already and return boolean value true or false as applied.If it does not contain then add that key into the map and its corresponding value should be 1 otherwise key would have already be contained in map so get the value of that key using get() and increment it by 1. Finally printing the map.
我们有一个包含 11 个数字的数组，逻辑是使用这些数字创建一个地图。其中地图的KEYS将是用户必须输入的实际数字，而不是。该实际编号的出现。将是该 KEY 的值。这里， containsKey() 方法检查映射是否已经包含该键并返回布尔值 true 或 false 作为应用。如果它不包含则将该键添加到映射中，其对应的值应为 1 否则键将已包含在地图中，因此使用 get() 获取该键的值并将其增加 1。最后打印地图。
OUTPUT:--
输出： -
Number 2 Occours 2 time, Number 4 Occours 3 time, Number 5 Occours 1 time, Number 6 Occours 2 time, Number 7 Occours 1 time, Number 8 Occours 2 time,
2号出现2次，4号出现3次，5号出现1次，6号出现2次，7号出现1次，8号出现2次，
回答by Diana
int intArray[] = {5, 1, 2, 3, 4, 5, 3, 2};
String val = "";
int c = 1;
Map<Integer, Integer> nwmap = new HashMap<Integer, Integer>();
for (int i = 0; i < intArray.length; i++) {
Integer key = intArray[i];
if(nwmap.get(key) != null && nwmap.containsKey(key)){
val += " Duplicate: " +String.valueOf(key)+"\n";
}else{
nwmap.put(key, c);
c++;
}
}
LOG.debug("duplicate value:::"+val);
回答by Patricia Shanahan
You are counting the number of pairs of indices that have equal values. What you claim to want is the total size of all sets of equal elements that have more than one element in them.
您正在计算具有相等值的索引对的数量。您声称想要的是其中包含多个元素的所有相等元素集的总大小。
I would use a Map or similar to count the total number of appearances of a given value. At the end, iterate over the key values adding the number of appearances for each key that has more than one appearance.
我会使用 Map 或类似的东西来计算给定值出现的总数。最后，迭代键值，为具有多个外观的每个键添加出现次数。
