面试题03. 数组中重复的数字

数组中重复的数字

题目描述

找出数组中重复的数字。

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

---

示例：

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

---

提示：
2 <= n <= 100000

转载来源：力扣（LeetCode）

---

题目分析

找重复，而且数字的范围都给出来了，而且数字的范围也不大，好办，创建一个大小为n的数组，哈希哈皮一下就好；
但是题目给出了一个条件“所有数字都在 0～n-1 的范围内”，这就有意思了，用来哈希存放的数字这下子都不用自己申请，直接用原数组就好，我看题解里的大牛们叫这种方法“原地哈皮（狗头）”，将普通哈希法的O(N)空间复杂度降到了O(1)，时间复杂度两者都是O(N)；
下面贴一下这个方法的代码：

fun findRepeatNumber(nums: IntArray): Int {
        return goodFind(nums)
    }
//普通方法
    fun normalFind(nums: IntArray): Int {
        val isExist = BooleanArray(nums.size){false}
        for (num in nums) {
            if(isExist[num])
                return num
            else
                isExist[num] = true
        }
        return 1
    }
//原地哈希法
    fun goodFind(nums:IntArray):Int{
        for(i in 0 until nums.size){
            if(nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    return nums[i]
                }
//                swap
                val tmp = nums[i]
                nums[i] = nums[nums[i]]
                nums[nums[i]] = tmp
            }
        }
        return 1
    }

代码文件

---