java - 在 Java 的输入数组中，如何找到相等值对的数量？

Question

我正在尝试制作一个 O(nlogn) 算法来确定对数 输入数组中相等的值。我想做的是将数组的每个值存储在另一个变量中，并继续将当前值与以前的值进行比较，看看是否匹配，如果匹配，则计数器加一。

int current value; 
int previous value; 
    for(int j = 0; j < array.length; j++){
        current value = array[k]
        previous value = array[k-1]

令我感到困惑的是运行时间必须为 O(nlogn)，所以我想知道这是否是解决此类问题的正确方法，或者是否有更好更方便的方法这样做的方式。

伪代码:

n = array.length
for k - 1 to n do
    if k == k-1 
    then
increment counter by 1

Answer 1

您可以对数组进行排序并比较相邻值，这是一种选择。那么你的复杂度将是 O(n*log(n))。

另一种选择是使用临时 HashSet 和结果 HashMap 作为对的计数器来跟踪已经访问过的元素:

public static <T> Map<T, Integer> findPairs(List<T> elements) {
    Set<T> tracked = new HashSet<>();
    Map<T, Integer> result = new HashMap<>();
    for (T element : elements)
        if (!tracked.add(element)) {
            result.merge(element, 1, Math::addExact);
            tracked.remove(element);
        }
    return result;
}

这个方法给你 O(n) 因为 HashSet 和 HashMap 的插入和删除是 O(1) 平均，但在最坏的情况下O(n)。如果在最坏的情况下 O(n*log(n)) 对您来说很重要，您应该选择第一个选项并相应地选择排序算法。一些排序算法的最坏情况复杂度为 O(n²)。