@liweiwei1419
2019-02-10T23:05:22.000000Z
字数 1040
阅读 1344
桶排序
传送门:AcWing:数组中重复的数字。
给定一个长度为 的整数数组
nums
,数组中所有的数字都在 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意:如果某些数字不在 的范围内,或数组中不包含重复数字,则返回 ;
样例:
给定
nums = [2, 3, 5, 4, 3, 2, 6, 7]
。返回 或 。
分析:在一个长度为 的数组里的所有数字都在 到 的范围内,找出数组中任意一个重复的数字。
能想到的最简单的思路有:1、排序;2、哈希表。
不过我们使用桶排序的思想来解决,思想就是把一个数放在它该放的位置上。
Python 代码:
# 3、数组中重复的数字
class Solution(object):
def duplicateInArray(self, nums):
"""
:type nums: List[int]
:rtype int
"""
l = len(nums)
if l == 0:
return -1
for num in nums:
if num < 0 or num >= l:
return -1
for i in range(l):
while nums[i] != i:
# 关键在这里,如果两个数一样,就没有必要交换了,直接就可以说,我找到这个元素
# 如果发现,马上要交换的这个数和自己是相等的,这就相当于找到了重复元素
if nums[i] == nums[nums[i]]:
return nums[i]
# 注意:千万不能这么写!!! nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
# self.__swap(nums, i, nums[i])
return -1
def __swap(self, nums, index1, index2):
if index1 == index2:
return
temp = nums[index1]
nums[index1] = nums[index2]
nums[index2] = temp
if __name__ == '__main__':
nums = [2, 3, 5, 4, 3, 2, 6, 7]
solution = Solution()
result = solution.duplicateInArray(nums)
print(result)
这个办法修改了数组。
扩展:LeetCode 第 287 题,传送门:寻找重复数。
(本节完)