【题解】【数组】【Leader】【Codility】Dominator

Find an index of an array such that its value occurs at more than half of indices in the array.

A zero-indexed array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.
For example, consider array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
Write a function that returns index of any element of array A in which the dominator of A occurs. The function should return ?1 if array A does not have a dominator.
the function may return 0, 2, 4, 6 or 7, as explained above.

Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

思路：

这题跟《编程之美》上的寻找发帖水王是一个问题，思路就是在一个数组中去除两个不相同的元素之后，原来n个数Leader还是新的n-2个数的Leader。遍历n个数，每次用一个Leader来抵消一个非Leader，然后记录下剩余Leader的数量。
最后还要验证下用这种方法选出来的Candidate是否真的是Leader。

代码：

 1 int solution(const vector<int> &A) {
 2     int size = 0;
 3     int leader = -1;
 4     for(int i = 0; i < A.size(); i++){
 5         if(size == 0)
 6             leader = A[i];
 7         if(A[i] != leader)
 8             size--;
 9         else
10             size++;
11     }
12     if(size == 0) return -1;
13     
14     int pos = -1;
15     int count = 0;
16     for(int i = 0; i < A.size(); i++){
17         if(A[i] == leader) {
18             count++;
19             pos = i;
20         }
21     }
22     if(count*2 <= A.size()) return -1;
23     return pos;
24 }

Dominator有个进阶题Equi-leader，大意是将数组一分为二，左右的Leader相同，求这样的分割点个数。乍一看以为要做多次Dominator的计算，有一点非常重要：

如果一个数在左右子数组中都是Leader，那么它必然也是原数组的Leader

因此我们只需找出原数组的Leader并记录Leader出现的次数c，然后再枚举分割点，求Leader在左子数组出现的次数n，再看n和c-n是否都能hold住各自的那一半数组就OK啦。

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. the function should return 2, as explained above.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [?1,000,000,000..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

【题解】【数组】【Leader】【Codility】Dominator

原文：http://www.cnblogs.com/wei-li/p/Dominator.html