Java - 查找数组中的最大重复项数

Question

我正在使用 HashSet 查找sorted Integer 数组中某个值的最大重复数。但是我的算法似乎不起作用，没有返回所需的结果。

Set variables storing the number of duplicates found (0), and the maximum number of duplicates (0). 
Set a HashSet that stores the unique values of an array.
Sort the array to be ready for comparison.

Loop through each value of the array
    If the HashSet of unique values contains the current value:
        Increment the duplicate Count

    If the currentValue is not equal to the previous value:
        If the duplicateCount is greater than the maximum Count:
            maximumCount becomes duplicateCount
            Reset duplicateCount to 0

Java 代码:

HashSet<Integer> uniqueValues = new HashSet<Integer>(valueSequenceList);

int duplicateCount = 0;
int maxCount = 0;
Arrays.sort(valueSequence);

for (int i = 0; i < valueSequence.length; i++)
{
    if (uniqueValues.contains(valueSequence[i]))
    {
        duplicateCount++;
    }
    if (i > 0 && valueSequence[i] != valueSequence[i-1])
    {
        if (duplicateCount > maxCount)
        {
            maxCount = duplicateCount;
            duplicateCount = 0;
        }
    }
}

示例:
输入:[4, 4, 10, 4, 10]
输出:4 个重复项(应该最多有 3 个重复项 - 相同值的总数)。

Answer 1

这是 Element Distinctness Problem - 在线程中有详细说明:Find duplicates in an array .

提到的线程讨论了问题的解决方案，并显示了下限(如果不使用哈希表，就不能比 O(nlogn) 做得更好。

因此，如果您的数据未排序 - 您可以排序和迭代(如下所示)，或使用哈希集 - 然后您不需要对数组进行排序。

如果您首先对数组进行排序，或者数组已经排序，则单次迭代将执行:

排序数组的单次迭代:

if (arr == null || arr.length == 0) return 0;
int last = arr[0];
int numDupes = 1;
for (int i = 1; i < arr.length; i++) { 
   if (arr[i] == last) numDupes++;
   last = arr[i];
}

使用 HashSet(无需排序):

if (arr == null) return 0;
Set<Integer> set = new HashSet<>();
int numDupes = 0;
for (int x : arr) { 
    if (set.contains(x)) numDupes++;
    set.add(x);
}

---

如果您正在寻找某些元素重复的最大次数(而不是重复的总数)，您可以使用相同的方法但略有不同:

哈希解决方案 - 使用 histogram :

Map<Integer,Integer> histogram = new HashMap<>();
for (int x : arr) { 
  if (!histogram.containsKey(x)) histogram.put(x,1); 
  else histogram.put(x,histogram.get(x) + 1);
}
int max = 0;
for (int x : histogram.values) max = max > x ? max : x;
return max;

排序数组解决方案:

if (arr == null || arr.length == 0) return 0;
int last = arr[0];
int max = 0;
int currNumDupes = 1;
for (int i = 1; i < arr.length; i++) { 
   if (arr[i] == last) currNumDupes++;
   else { 
        max = max > currNumDupes ? max : currNumDupes;
        currNumDupes = 1;
   }
   last = arr[i];
}
max = max > currNumDupes ? max : currNumDupes; //if the most dupes is from the highest element