我试图做一个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

最佳答案

您可以对数组进行排序并比较相邻的值,这是一种选择。这样,您将具有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),因为从HashSetHashMap进行插入和删除操作平均为O(1),但在最坏的情况下为O(n)。如果在最坏的情况下使用O(n*log(n))对您很重要,则应选择第一个选项,并相应地选择排序算法。一些排序算法将O(n2)作为最坏情况的复杂度。

09-10 03:44
查看更多