Codility 8.2 EquiLeader [leader]

Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same.

Task description
A non-empty 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:

def solution(A)

that, given a non-empty 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.

Write an efficient algorithm for the following assumptions:

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

思路：这道题是Dominator的拓展，意思是将数组一分为二，左右的Leader相同，求这样的分割点个数。
这道题不用求三次Leader，只要求一次。因为：如果一个数在左右子数组中都是Leader，那么它必然也是原数组的Leader。
因此我们只需找出原数组的Leader并记录Leader出现的次数leader_count，然后再枚举分割点，求Leader在左子数组出现的次数leader_left，再看leader_left和leader_count - leader_left是否都大于各自的数组一半长。

#66%
#Detected time complexity:
#O(N ** 2)
def solution1(A):
    # write your code in Python 3.6
    size = 0
    leader = -1
    index = -2
    result = 0
    count_left = 0
    
    for i in range(len(A)):
        if size ==0:
            leader = A[i]
            size +=1
            index +=1
        else:
            if leader !=A[i]:
                size -=1
            else:
                size+=1
    leader_count = len([i for i in A if i == leader]) # count
    if leader_count <= len(A)//2:
        return 0
        
    for i in range(len(A)-1):
        if A[i] == leader:
            count_left +=1
        if count_left>len(A[:i+1])//2 and leader_count-count_left>len(A[i+1:])//2:
            result +=1   
    return result

#Detected time complexity:
#O(N)
#100%
def solution2(A):
    # write your code in Python 3.6

    A_len = len(A)
    candidate = -1
    candidate_count = 0
    candidate_index = -1
    # Find out a leader candidate
    for index in range(A_len):
        if candidate_count == 0:
            candidate = A[index]
            candidate_index = index
            candidate_count += 1
        else:
            if A[index] == candidate:
                candidate_count += 1
            else:
                candidate_count -= 1
    # Make sure the candidate is the leader
    leader_count = len([number for number in A if number == candidate])
    if leader_count <= A_len//2:
        # The candidate is not the leader
        return 0
    else:
        leader = candidate
    equi_leaders = 0
    leader_count_so_far = 0
    for index in range(A_len):
        if A[index] == leader:
            leader_count_so_far += 1
        if leader_count_so_far > (index+1)//2 and leader_count-leader_count_so_far > (A_len-index-1)//2:
            # Both the head and tail have leaders of the same value
            # as "leader"
            equi_leaders += 1
    return equi_leaders

复杂度分析：def1是我写的，时间复杂度为O(N**2)，def2来源于code says，时间复杂度为O(N)，这里分析一下原因：用了大量的len(A)以及slice。
首先，能用常数就不用len(A)，可以用for i in A 或者len_a = len(A)，因为每个len() 都是O(N)。
其次，慎重用len(a[i：])和len(a[：i])，这是在不停的在产生slice的copy，是整个程序里面最大的开销。
最后，不要随便用count啊，每一次count都是一次遍历，复杂度是O(n)
总之，能用常数就不用built-in func。
程序最终版，Detected time complexity:O(N)

    # write your code in Python 3.6
    A= [4,3,4,4,4,2]
    len_A = len(A)
    size = 0
    leader = -1
    index = -2
    result = 0
    count_left = 0
    
    for i in A:
        if size ==0:
            leader = i
            size +=1
            index +=1
        else:
            if leader ==i:
                size +=1
            else:
                size-=1
    leader_count = len([i for i in A if i == leader]) # count
    if leader_count <= len_A//2:
        return 0
        
    for i in range(len_A):
        if A[i] == leader:
            count_left +=1
        if count_left>(i+1)//2 and leader_count-count_left>(len_A-i-1)//2:
            result +=1   
    return result