[关闭]
@liweiwei1419 2019-02-10T15:05:22.000000Z 字数 1040 阅读 1230

《剑指 Offer》(第 2 版)第 3 题:数组中重复的数字

桶排序


传送门:AcWing:数组中重复的数字

给定一个长度为 的整数数组 nums,数组中所有的数字都在 的范围内。

数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意:如果某些数字不在 的范围内,或数组中不包含重复数字,则返回

样例:

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]

返回

分析:在一个长度为 的数组里的所有数字都在 的范围内,找出数组中任意一个重复的数字。

能想到的最简单的思路有:1、排序;2、哈希表。

不过我们使用桶排序的思想来解决,思想就是把一个数放在它该放的位置上。

Python 代码:

  1. # 3、数组中重复的数字
  2. class Solution(object):
  3. def duplicateInArray(self, nums):
  4. """
  5. :type nums: List[int]
  6. :rtype int
  7. """
  8. l = len(nums)
  9. if l == 0:
  10. return -1
  11. for num in nums:
  12. if num < 0 or num >= l:
  13. return -1
  14. for i in range(l):
  15. while nums[i] != i:
  16. # 关键在这里,如果两个数一样,就没有必要交换了,直接就可以说,我找到这个元素
  17. # 如果发现,马上要交换的这个数和自己是相等的,这就相当于找到了重复元素
  18. if nums[i] == nums[nums[i]]:
  19. return nums[i]
  20. # 注意:千万不能这么写!!! nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
  21. nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
  22. # self.__swap(nums, i, nums[i])
  23. return -1
  24. def __swap(self, nums, index1, index2):
  25. if index1 == index2:
  26. return
  27. temp = nums[index1]
  28. nums[index1] = nums[index2]
  29. nums[index2] = temp
  30. if __name__ == '__main__':
  31. nums = [2, 3, 5, 4, 3, 2, 6, 7]
  32. solution = Solution()
  33. result = solution.duplicateInArray(nums)
  34. print(result)

这个办法修改了数组。

扩展:LeetCode 第 287 题,传送门:寻找重复数
(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注