用分治法解决摩尔投票的问题(python表达)

redleafage

这是一道程序填空题，题目要求：给定一个长度为n数列a，如果数列a中存在一个元素值的数量大于n/2，即存在一个数的数量超过一半，则返回1，否则返回0.题目要求用分治法处理，时间复杂度为o(nlogn)
比如输入：
5
1 2 2 3 4
返回0

输入：
5
1 2 2 2 3 （存在一个2的数量大于数列总数的一半）
返回1

题目填充框架：

1. # Uses python3
   
2. import sys
   
3. 
   
4. def get_majority_element(a, left, right):
   
5.     if left == right:
   
6.         return -1
   
7.     if left + 1 == right:
   
8.         return a[left]
   
9.     #write your code here
   
10.     return -1
    
11. 
    
12. if __name__ == '__main__':
    
13.     input = sys.stdin.read()
    
14.     n, *a = list(map(int, input.split()))
    
15.     if get_majority_element(a, 0, n) != -1:
    
16.         print(1)
    
17.     else:
    
18.         print(0)
    

复制代码

我的思路是：
如果存在一个数超过总数的一半，那么把这个数列分成两半，则其中一半必有这个数同样是这一半的过半数，依此递归合拢。
我的代码如下：

1. #Users python3
   
2. __Author__ = 'Redleafage Zhang'
   
3. import sys
   
4. 
   
5. def get_majority_element(a, left, right):
   
6.     list = []
   
7.     if left == right:
   
8.         return -1
   
9.     if left + 1 == right:
   
10.         return a[left]
    
11. 
    
12. 
    
13.     #write your code here
    
14.     mid = (left+right) // 2
    
15.     major_l = get_majority_element(a,left,mid)
    
16.     major_r = get_majority_element(a,mid+1,right)
    
17.     if  major_l == major_r:
    
18.         return major_l
    
19.     else:
    
20.         if a.count(major_l) > right//2:
    
21.             return major_l
    
22.         if a.count(major_r) > right//2:
    
23.             return major_r
    
24.     return -1
    
25. 
    
26. if __name__ == '__main__':
    
27.     input = sys.stdin.read()
    
28.     n, *a = list(map(int, input.split()))
    
29.     if get_majority_element(a, 0, n) != -1:
    
30.         print(1)
    
31.     else:
    
32.         print(0)
    
33. 
    

复制代码

这个代码测试的结果没问题，但是无法通过测验，提示我超时：
Failed case #11/21: time limit exceeded (Time used: 9.96/5.00, memory used: 21278720/536870912.)

请教各位鱼油，我该如何优化这个代码呢？非常感谢！

alltolove

不要用递归，要用迭代速度会快点

redleafage

alltolove 发表于 2018-7-6 08:22
不要用递归，要用迭代速度会快点

我知道这道题如果不用递归有更快的算法，但我想锻炼一下递归思维，想用分治法把这题解出来。而且这道题如果递归运用正确，是可以通过测验的。题目要求这道题时间复杂度只要达到o(nlogn)就可以通过测试，所以我很想知道我的代码问题出在哪里？导致交题时判断我的代码超时?

xy123963

好难，看了半天还是不会，

redleafage

xy123963 发表于 2018-7-9 16:28
好难，看了半天还是不会，

这题我已经自己想出来了。。

xy123963

redleafage 发表于 2018-7-9 16:47
这题我已经自己想出来了。。

，能不能贴个答案，学习学习

redleafage

xy123963 发表于 2018-7-9 16:49
，能不能贴个答案，学习学习

1. #Users python3
   
2. __Author__ = 'Redleafage Zhang'
   
3. import sys
   
4. 
   
5. def get_majority_element(a, left, right):
   
6.     list = []
   
7.     if left == right:
   
8.         return -1
   
9.     if left + 1 == right:
   
10.         return a[left]
    
11. 
    
12. 
    
13.     #write your code here
    
14.     mid = (left+right) // 2
    
15.     major_l = get_majority_element(a,left,mid)
    
16.     major_r = get_majority_element(a,mid+1,right)
    
17.     if  major_l == major_r:
    
18.         return major_l
    
19.     else:
    
20.         if a[left:right+1].count(major_l) > len(a[left:right+1])//2:
    
21.             return major_l
    
22.         if a[left:right+1].count(major_r) > len(a[left:right+1])//2:
    
23.             return major_r
    
24.     return -1
    
25. 
    
26. if __name__ == '__main__':
    
27.     input = sys.stdin.read()
    
28.     n, *a = list(map(int, input.split()))
    
29.     if get_majority_element(a, 0, n) != -1:
    
30.         print(1)
    
31.     else:
    
32.         print(0)
    

复制代码

xy123963

独吟月上

multitate

ck567

常德水鱼村

支持楼主！楼主加油！