用分治法解决摩尔投票的问题(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

题目填充框架：

# Uses python3
import sys

def get_majority_element(a, left, right):
    if left == right:
        return -1
    if left + 1 == right:
        return a[left]
    #write your code here
    return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    if get_majority_element(a, 0, n) != -1:
        print(1)
    else:
        print(0)

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

#Users python3
__Author__ = 'Redleafage Zhang'
import sys

def get_majority_element(a, left, right):
    list = []
    if left == right:
        return -1
    if left + 1 == right:
        return a[left]


    #write your code here
    mid = (left+right) // 2
    major_l = get_majority_element(a,left,mid)
    major_r = get_majority_element(a,mid+1,right)
    if  major_l == major_r:
        return major_l
    else:
        if a.count(major_l) > right//2:
            return major_l
        if a.count(major_r) > right//2:
            return major_r
    return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    if get_majority_element(a, 0, n) != -1:
        print(1)
    else:
        print(0)

这个代码测试的结果没问题，但是无法通过测验，提示我超时：
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
，能不能贴个答案，学习学习

#Users python3
__Author__ = 'Redleafage Zhang'
import sys

def get_majority_element(a, left, right):
    list = []
    if left == right:
        return -1
    if left + 1 == right:
        return a[left]


    #write your code here
    mid = (left+right) // 2
    major_l = get_majority_element(a,left,mid)
    major_r = get_majority_element(a,mid+1,right)
    if  major_l == major_r:
        return major_l
    else:
        if a[left:right+1].count(major_l) > len(a[left:right+1])//2:
            return major_l
        if a[left:right+1].count(major_r) > len(a[left:right+1])//2:
            return major_r
    return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    if get_majority_element(a, 0, n) != -1:
        print(1)
    else:
        print(0)

xy123963

独吟月上

multitate

ck567

常德水鱼村

支持楼主！楼主加油！