Codility 8.1 Dominator [leader]

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

Task description
An 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

def solution(A)

that, given an 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.

For example, given 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 function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

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

思路：要找出现超过一半次数的数，那么可以遍历数组，每次用一个leader来抵消一个非leader，然后记录下剩下的这个Leader。（！！！在一个数组中去除两个不相同的元素之后，原来n个数Leader还是新的n-2个数的Leader。）
注意：最后还要验证下这个剩下的leader是否真的是Leader。例如[1,2,1,3,4]，剩下4，就不是真的leader。

def solution(A):
    # write your code in Python 3.6
    size = 0
    leader = -1
    index = -1
    for i in range(len(A)):
        if size ==0:
            leader = A[i]
            size +=1
            index = i
        else:
            if A[i]!=leader:
                size -=1
            else:
                size +=1
    #检验leader是否是真的leader
    if A.count(leader)<= len(A)//2:
        return -1
    else:
        return index