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
网友评论