Algorithms Count all pairs of equal numbers in a sorted array in O (n)?

Question

The question I'm thinking about is this:

Say we have a sorted array with numbers {1,1,1,1,2,2,4,4,4}.

Now, given that we can clearly see that we have six pairs of 1, one pair of two and three pairs of 4 (10 pairs). How would you build an algorithm that finds these pairs in O (n)?

I have an algorithm that counts pairs in an array and does it like this:

Arrays.sort(array);
int counter = 0; 
for(int i = 0; i<array.length; i++) {
     for(int j = i+1; j<array.length; j++) {
          if(j!=i && array[j] == array[i]) {
	counter++;
	}
      }
}
return counter; 

Run codeHide result

But this works in O (N ^ 2), and I assume (being a beginner that I am with algorithms) that there is a better solution to get the same results using only one for or loop while loop?

I would love to hear your thoughts!

Answer 1

O(N):

int pairs = 0; 
int times = 1;
for (int i = 1; i < array.length; ++i) {
    if (array[i] == array[i-1]) {
        ++times;
    } else {
        pairs += times*(times-1) / 2;
        times = 1;
    }                   
}
pairs += times*(times-1) / 2;
return pairs;       

Runnable: https://ideone.com/mu65ie

times. C(times, 2) = times*(times-1) / 2.

Answer 2

, :

 int i = 0;
 int pairs = 0;

 while (i < array.length - 1) {
    if(array[i] == array[i + 1]) {
        pairs += 1;
        i += 2;
    } else {
        i++;
    }
 }

, , . O(n).

, , sorted.

Answer 3

, . . , O (nlogn).

, , , . , O (n).

wikipedia , , , , :

n! / (k! * (n - k)!)

! , n , (4 1s), k (2 ). :

4! = 24
2! = 2
(4-2)! = 2
4!/(2!2!) = 24/4 = 6

, O (n). , , . - !

, python 3, , python 2. , .

(memoization):

import math

class Cache(object):
    memos = dict()

    def factorial(self, n):
         if not n in self.memos:
             self.memos[n] = math.factorial(n)
         return self.memos[n]

Answer 4

What about:

    Arrays.sort(array);
    int counter = 0; 
    for(int i = 1; i<array.length; i++) {
        if(array[i] == array[i-1]) {
            counter++;
            ++i;
        }
    }
    return counter;

Answer 5

This is my way of doing it. Hope this helps someone :)

static int foo(int[] ar) {      
    int count = 0;
    Arrays.sort(ar);
    for(int i = 0; i<ar.length-1;i++)
    {
            if(ar[i] == ar[i+1])
            {
                count ++;
                i++;
            }
    }
    return count;

}