我试图做一个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)
,因为从HashSet
和HashMap
进行插入和删除操作平均为O(1)
,但在最坏的情况下为O(n)
。如果在最坏的情况下使用O(n*log(n))
对您很重要,则应选择第一个选项,并相应地选择排序算法。一些排序算法将O(n2)作为最坏情况的复杂度。