鱼C论坛

 找回密码
 立即注册
查看: 3877|回复: 11

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

[复制链接]
发表于 2018-7-5 23:35:09 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
这是一道程序填空题,题目要求:给定一个长度为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. def get_majority_element(a, left, right):
  4.     if left == right:
  5.         return -1
  6.     if left + 1 == right:
  7.         return a[left]
  8.     #write your code here
  9.     return -1

  10. if __name__ == '__main__':
  11.     input = sys.stdin.read()
  12.     n, *a = list(map(int, input.split()))
  13.     if get_majority_element(a, 0, n) != -1:
  14.         print(1)
  15.     else:
  16.         print(0)
复制代码


我的思路是:
如果存在一个数超过总数的一半,那么把这个数列分成两半,则其中一半必有这个数同样是这一半的过半数,依此递归合拢。
我的代码如下:
  1. #Users python3
  2. __Author__ = 'Redleafage Zhang'
  3. import sys

  4. def get_majority_element(a, left, right):
  5.     list = []
  6.     if left == right:
  7.         return -1
  8.     if left + 1 == right:
  9.         return a[left]


  10.     #write your code here
  11.     mid = (left+right) // 2
  12.     major_l = get_majority_element(a,left,mid)
  13.     major_r = get_majority_element(a,mid+1,right)
  14.     if  major_l == major_r:
  15.         return major_l
  16.     else:
  17.         if a.count(major_l) > right//2:
  18.             return major_l
  19.         if a.count(major_r) > right//2:
  20.             return major_r
  21.     return -1

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

复制代码


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

请教各位鱼油,我该如何优化这个代码呢?非常感谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-7-6 08:22:31 | 显示全部楼层
不要用递归,要用迭代速度会快点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-7-6 08:43:27 From FishC Mobile | 显示全部楼层
alltolove 发表于 2018-7-6 08:22
不要用递归,要用迭代速度会快点

我知道这道题如果不用递归有更快的算法,但我想锻炼一下递归思维,想用分治法把这题解出来。而且这道题如果递归运用正确,是可以通过测验的。题目要求这道题时间复杂度只要达到o(nlogn)就可以通过测试,所以我很想知道我的代码问题出在哪里?导致交题时判断我的代码超时?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-7-9 16:28:17 | 显示全部楼层

回帖奖励 +5 鱼币

好难,看了半天还是不会,
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-7-9 16:47:21 | 显示全部楼层
xy123963 发表于 2018-7-9 16:28
好难,看了半天还是不会,

这题我已经自己想出来了。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-7-9 16:49:35 | 显示全部楼层
redleafage 发表于 2018-7-9 16:47
这题我已经自己想出来了。。

,能不能贴个答案,学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-7-9 16:52:06 | 显示全部楼层
xy123963 发表于 2018-7-9 16:49
,能不能贴个答案,学习学习
  1. #Users python3
  2. __Author__ = 'Redleafage Zhang'
  3. import sys

  4. def get_majority_element(a, left, right):
  5.     list = []
  6.     if left == right:
  7.         return -1
  8.     if left + 1 == right:
  9.         return a[left]


  10.     #write your code here
  11.     mid = (left+right) // 2
  12.     major_l = get_majority_element(a,left,mid)
  13.     major_r = get_majority_element(a,mid+1,right)
  14.     if  major_l == major_r:
  15.         return major_l
  16.     else:
  17.         if a[left:right+1].count(major_l) > len(a[left:right+1])//2:
  18.             return major_l
  19.         if a[left:right+1].count(major_r) > len(a[left:right+1])//2:
  20.             return major_r
  21.     return -1

  22. if __name__ == '__main__':
  23.     input = sys.stdin.read()
  24.     n, *a = list(map(int, input.split()))
  25.     if get_majority_element(a, 0, n) != -1:
  26.         print(1)
  27.     else:
  28.         print(0)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-7-10 08:52:23 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-7-10 16:03:47 | 显示全部楼层

回帖奖励 +5 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-7-11 20:22:48 | 显示全部楼层

回帖奖励 +5 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-8-15 12:13:05 | 显示全部楼层

回帖奖励 +5 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-9-14 08:43:48 | 显示全部楼层

回帖奖励 +5 鱼币

支持楼主!楼主加油!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 22:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表