Massive Algorithms: Rafal's Blog - Codility Equi-Leader

A non-empty zero-indexed array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

    A[0] = 4
    A[1] = 3
    A[2] = 4
    A[3] = 4
    A[4] = 4
    A[5] = 2

we can find two equi leaders:

0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.

2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the number of equi leaders.

For example, given:

    A[0] = 4
    A[1] = 3
    A[2] = 4
    A[3] = 4
    A[4] = 4
    A[5] = 2

the function should return 2, as explained above.

The key idea that wasn't allowing me to come up with a good solution is the following: If you have an array A which has leader x (the leader is the unique element that occurs more than in half of the array), then for every separation of A into A[0..i),A[i..n), if they have the same leader, then the leader of both is x. This follows from noticing that if z is a leader in A[0..i), then it occurs more than ⌈i2⌉ elements, and similarly, if z is the leader of A[i..n), then x occurs more than ⌈n−i2⌉. In total, if both slices have leader z, it must occur more than ⌈n2⌉, which means that y=x as required.

http://www.cnblogs.com/lautsie/p/3424431.html

一开始想到从左和右两边开始扫取众数，但求众数又要重新扫一遍，这样复杂度就是O(n^2)了。
此题的关键在于Equi-Leader必然是众数，否则不可能左边和右边都是众数。
所以先求出众数及其出现次数，再扫就行了。

static int equiLeader(int[] a){
  int len = a.length;
  int equi_leaders = 0;

  // first, compute the leader
  int leader = a[0];
  int ctr = 1;

  for(int i = 1; i < a.length; i++){
    if(a[i] == leader) ctr++;
    else ctr--;
    if(ctr == 0){
      ctr = 1;
      leader = a[i];
    }
  }

  // check if it's a leader?
  int total = 0;
  for(int i : a){
    if(i == leader) total++; 
  }

  if(total <= (len/2)) return 0; // impossible

  int ldrCount = 0;
  for(int i = 0; i < a.length; i++){
    if(a[i] == leader) ldrCount++;
    int leadersInRightPart = (total - ldrCount);
    if(ldrCount > (i+1)/2   &&   leadersInRightPart > (len-i-1)/2){
      equi_leaders++;
    }
  }

  return equi_leaders;
}