【LeetCode】剑指 Offer 03. 数组中重复的数字

题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
 

限制：

2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解答

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for _idx in range(0, len(nums)):
            while nums[_idx] != _idx:

                if nums[nums[_idx]] == nums[_idx]:
                    return nums[_idx]

                temp = nums[_idx]
                nums[_idx] = nums[temp]
                nums[temp] = temp

题目的解法有多种：

1、先排序后计数；

2、用hash计数，额外空间O(N)，时间O(N)

3、鸽巢原理，额外空间O(1)，时间O(N)

---

拓展

思考如果要找到所有重复数字：

（还有个小问题，未处理同样值多输出）

# coding:utf-8
"""
题目：
    现有整数数组a大小为n，每个元素 0 <= ai < n，其中每个值可能出现一次货两次，求出现值两次的元素
Demo：
    输入：
        2 3 4 1 3
    输出：
        3
"""


class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for _idx in range(0, len(nums)):
            while nums[_idx] != _idx:
                # temp = nums[_idx]
                # print(_idx, nums[_idx], nums[temp])
                if nums[nums[_idx]] == nums[_idx]:
                    print(nums[_idx])
                    break

                temp = nums[_idx]
                nums[_idx] = nums[temp]
                nums[temp] = temp


if __name__ == "__main__":
    Solution().findRepeatNumber([1,2,3,4,1,3,2])
    # Solution().findRepeatNumber([1,3,2,4,1,0,3])
    # Solution().findRepeatNumber([2,3,4,3,2])

稍微难一点的变种