论坛 › 数据结构与算法 › 用分治法解决摩尔投票的问题(python表达)

redleafage 发表于 2018-7-5 23:35:09

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

这是一道程序填空题，题目要求：给定一个长度为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
    #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


    #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)
    ifmajor_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 发表于 2018-7-6 08:22:31

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

redleafage 发表于 2018-7-6 08:43:27

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

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

xy123963 发表于 2018-7-9 16:28:17

好难，看了半天还是不会，{:5_100:}

redleafage 发表于 2018-7-9 16:47:21

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

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

xy123963 发表于 2018-7-9 16:49:35

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

{:5_106:}，能不能贴个答案，学习学习{:5_101:}

redleafage 发表于 2018-7-9 16:52:06

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


    #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)
    ifmajor_l == major_r:
      return major_l
    else:
      if a.count(major_l) > len(a)//2:
            return major_l
      if a.count(major_r) > len(a)//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 发表于 2018-7-10 08:52:23

{:5_110:}{:5_110:}{:5_110:}

独吟月上 发表于 2018-7-10 16:03:47

{:5_109:}{:5_109:}

multitate 发表于 2018-7-11 20:22:48

{:5_90:}{:5_103:}{:5_106:}

ck567 发表于 2018-8-15 12:13:05

{:5_90:}

常德水鱼村 发表于 2018-9-14 08:43:48

支持楼主！楼主加油！

查看完整版本: 用分治法解决摩尔投票的问题(python表达)