Python数组中重复的数字

本文阅读 3 分钟
首页 Python笔记 正文

对于一个长度为n的数组里所有的数字都在0到n-1的范围内。查找重复数字的话,首先容易想到,对数组进行排序,然后遍历数组查找重复的数字,这样的时间复杂度为O(nlogn);或者建立一个哈希表,这样实在O(n)的时间查找到,但是空间复杂度O(n)。另外一个空间复杂度为O(1)的算法如下,因为数字在0~n-1的范围内,那么如果数字没有重复,那么当数组排序之后数字i将出现在下标为i的位置,但是有重复的话,在某个位置j出现的数字将不是j。我们重排这个数组。从头到尾依次扫描这个数组中的每个数字,如果下标i不是出现数字i,那么就把数字i和i处的数字进行交换使数字i出现在应该出现的位置,如果新交换的数字还不是他应该出现的位置,继续交换,直至该处的数字m等于x下标m,如果在交换的过程中,第i处的位置数字等于第m处的数字,那么我们就找到了第一个重复的数字,记录这个数字,在从下一个位置继续扫描。

  1. '''
  2. 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
  3. 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。
  4. 请找出数组中任意一个重复的数字。
  5. 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
  6. '''
  7. # -*- coding:utf-8 -*-
  8. class Solution:
  9. # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
  10. # 函数返回True/False
  11. def duplicate(self, numbers, duplication):
  12. if numbers == None or len(numbers) <= 0:
  13. return False
  14. for i in numbers:
  15. if i < 0 or i > len(numbers) - 1:
  16. return False
  17. for i in range(len(numbers)):
  18. while numbers[i] != i:
  19. if numbers[i] == numbers[numbers[i]]:
  20. duplication[0] = numbers[i]
  21. return True
  22. else:
  23. index = numbers[i]
  24. numbers[i], numbers[index] = numbers[index], numbers[i]
  25. return False
  26. # 输出所有重复的数字
  27. def duplicate2(self, numbers):
  28. if numbers == None or len(numbers) <= 0:
  29. return False
  30. for i in numbers:
  31. if i < 0 or i > len(numbers) - 1:
  32. return False
  33. repeatedNums = []
  34. for i in range(len(numbers)):
  35. while numbers[i] != i:
  36. if numbers[i] == numbers[numbers[i]]:
  37. repeatedNums.append(numbers[i])
  38. break
  39. else:
  40. index = numbers[i]
  41. numbers[i], numbers[index] = numbers[index], numbers[i]
  42. return repeatedNums
  43. test = [2, 3, 1, 0, 2, 5, 3]
  44. s = Solution()
  45. dupulication = [0]
  46. print(s.duplicate(test,dupulication))
  47. print(s.duplicate2(test))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python树中两个节点的最低公共祖先
« 上一篇 01-21
Python构建乘积数组
下一篇 » 01-21

发表评论