In an input array in Java, how do I find the number of pairs of values that are equal?

Question

I'm trying to make an O(nlogn) algorithm that determines the number of pairs of values in an input array that are equal. What I was thinking of doing was storing each value of the array in another variable and continue comparing the current value to the previous values and see if there's a match and if there is then the counter goes up by one.

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

What I'm confused about is the fact that the running time has to be O(nlogn) so I'm wondering if that's the right kind of method to use for a problem like this or if there's a better and more convenient way of doing this.

Pseudo code:

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

What exactly do you mean by "pairs that are equal"? How many pairs would you say { 1, 2, 2, 2, 3, 2, } has? — azurefrog
– azurefrog, Commented Sep 30, 2015 at 2:57
It's supposed to find two numbers that are equal in the array and once it finds those two numbers then it counts that as one pair that are equal. So in this example it has 2 pairs that are equal. — Josh Susa
– Josh Susa, Commented Sep 30, 2015 at 2:59
It's very easy if the array is sorted. Are you allowed to sort the array? — Paul Boddington
– Paul Boddington, Commented Sep 30, 2015 at 3:05

Denis Bazhenov · Accepted Answer · 2015-09-30 03:25:10Z

You can sort array and compare adjacent values, it's one option. You'll have complexity of O(n*log(n)) then.

Another option is to track already visited elements using temporary HashSet and result HashMap as a counter for pairs:

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; }

This methods gives you O(n) because insertion and removal from HashSet and HashMap is O(1) on average, but O(n) in worst case. If it's important for you to have O(n*log(n)) in worst case you should select first option as well as select sorting algorithm accordingly. Some sorting algorithms have O(n²) as a worst case complexity.

Collectives™ on Stack Overflow

In an input array in Java, how do I find the number of pairs of values that are equal?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related