免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2153 | 回复: 2

两道比较复杂的轩辕互动面试题(Python实现) [复制链接]

论坛徽章:
0
发表于 2011-04-11 13:33 |显示全部楼层
1.平衡点问题
  平衡点:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24,25后面的总和也是24,25这个点就是平衡点;假如一个数组中的元素,其前面的部分等于后面的部分,那么这个点的位序就是平衡点
要求:返回任何一个平衡点
下面是代码:
  1.   1 li = [1,3,5,7,8,25,4,20]
  2.   2 def main():
  3.   3     i = 0
  4.   4     length = len(li)
  5.   5     before = 0
  6.   6     after = 0
  7.   7     mark = 0
  8.   8     balance = 0
  9.   9     total = sum(li)
  10. 10     while True:
  11. 11         balance = i + 1
  12. 12         if balance + 1 > length -1:
  13. 13             return -1
  14. 14         if li[i] == li[balance+1]:
  15. 15             mark = balance
  16. 16             return (mark,li[mark])
  17. 17         else:
  18. 18             before = before + li[i]
  19. 19             other = total - before - li[balance]
  20. 20             if before == other:
  21. 21                 mark = balance
  22. 22                 return (mark,li[mark])
  23. 23         i += 1
  24. 24 if __name__ == "__main__":
  25. 25    print  main()
复制代码
2.支配点问题:
支配数:数组中某个元素出现的次数大于数组总数的一半时就成为支配数,其所在位序成为支配点;比如int[] a = {3,3,1,2,3};3为支配数,0,1,4分别为支配点;
要求:返回任何一个支配点
本问题可归结为众数问题(统计学范畴),即一组数据中出现次数最多的那个数值,它可以没有也可以为多个。
下面是代码,如果你又更号的实现,不吝赐教。
  1.   1 li = [1,3,4,3,3]
  2.   2 def main():
  3.   3     mid = len(li)/2
  4.   4     for l in li:
  5.   5         count = 0
  6.   6         i = 0
  7.   7         mark = 0
  8.   8         while True:
  9.   9             if l == li[i]:
  10. 10                 count += 1
  11. 11                 temp = i
  12. 12             i += 1
  13. 13             if count > mid:
  14. 14                 mark = temp
  15. 15                 return (mark,li[mark])
  16. 16             if i > len(li) - 1:
  17. 17                 break
  18. 18      else:
  19. 19          return -1
  20. 20 if __name__ == "__main__":
  21. 21    print  main()
复制代码
最后,还有个一个中位数的问题,在很多笔试中也会遇到。
中位数:即数据从小到大排列,将数据分为两部分,一部分大于该数值,一部分小与该数值。中位数的位置是这样计算的:如果数据长度为奇数,中位数的位置为(N+1)/2,如果为偶数则为第N/2个数与第(N/2)+1的平均数。

论坛徽章:
0
发表于 2011-04-11 21:24 |显示全部楼层
第一个,貌似以数组中间的元素为分界,分别求两边的 subarray 的和,比较之后再决定将分界左移或者右移,然后重复求和和比较。这样应该更快一些。

后面的一个,如果先对数据做个排序,那么支配数应该出现在 array[len(array)/2] 上 (没细做推论),这样算法复杂度会降低不少。

LZ的代码看起来确实比较简洁,但 for 里面在来一个 while True, 实际上算法复杂度并不低。

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:50:28
发表于 2011-04-12 16:19 |显示全部楼层
第一个,貌似以数组中间的元素为分界,分别求两边的 subarray 的和,比较之后再决定将分界左移或者右移,然 ...
tubocurarine 发表于 2011-04-11 21:24



  第二个问题,用你的方法无法确定没有支配数出现的情况。
比如[1,2,3,4,4]
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP