《剑指 Offer》（第 2 版）第 3 题：数组中重复的数字

桶排序

传送门：AcWing：数组中重复的数字。

给定一个长度为 $n$ 的整数数组 nums，数组中所有的数字都在 $0∼n−1$ 的范围内。

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

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

注意：如果某些数字不在 $0∼n−1$ 的范围内，或数组中不包含重复数字，则返回 $-1$；

样例：

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

返回 $2$ 或 $3$。

分析：在一个长度为 $n$ 的数组里的所有数字都在 $0$ 到 $n-1$ 的范围内，找出数组中任意一个重复的数字。

能想到的最简单的思路有：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 题，传送门：寻找重复数。
（本节完）