Task description

A zero-indexed array A consisting of N integers is given. The dominatorof 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] =  3A[3] = 2    A[4] = 3    A[5] = -1A[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

int solution(const vector<int> &A);

that, given a zero-indexed array A consisting of N integers, 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.

Assume that:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

For example, given array A such that

 

A[0] = 3    A[1] = 4    A[2] =  3A[3] = 2    A[4] = 3    A[5] = -1A[6] = 3    A[7] = 3

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).

就是找一个数组的众数（出现次数大于N/2)。

主要利用这样一个特性：每次删掉不相同的两个元素，因为删掉两个不同的元素之后，数组里剩下的元素的众数还是原数组的众数。(The leader in the new sequence occurs more than n/2 − 1 = (n−2)/2 times )

有了上面的特性那程序就很好实现了：

// you can also use includes, for example:// #include 
     
      #include 
      
       int solution(const vector
       
         &A) {    // write your code in C++98    stack
        
          sstack;    for(int i=0;i
         
          A.size()/2) {            return candidate;        }else {            return -1;        }    }}
         
        
       
      
     

其实用栈有点浪费空间，因为栈里的元素肯定是一样的，所以只需要两个变量分别记录下栈的大小以及栈内元素的值就好。

需要注意的是最后需要检查一下栈顶的那个元素到底是不是众数。（因为比方说数组是1,2,3. 最后栈里留下的3显然不是众数）。

Leader这个lesson还有一个题是EquiLeader：

Task description

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(vector<int> &A);

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.

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).

还是个找众数的题，只是这一次需要完成的目标是：找出一个数组有多少个分割点，这个分割点使得左右两边的子数组的众数相同。

显然左右两边的子数组如果他们有相同的众数的话，那这个众数肯定是原数组的众数。

所以可以先找出原来的众数，然后重新遍历，判断当前的位置是不是一个有效的分割点就好。

// you can also use includes, for example:// #include 
     
      #include 
      
       int solution(vector
       
         &A) {    // write your code in C++98    stack
        
          sstack;    int count = 0;    int res = 0;    for(int i=0;i
         
          A.size()/2) {            int leftCount = 0;            for(int i=0;i
          
           (i+1)/2 && (count-leftCount)>(A.size()-i-1)/2) { res++; } } return res; } return 0; }}