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

题目

找出数组中重复的数字。

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

示例 1：

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

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

解题思路

• 题目中指出所有数字都在 0～n-1 的范围内，所以可以使用数组下标来作为HashMap的索引
• 通过遍历数组和交换操作让值和索引相互对应，就可以通过交换时判断重复值

算法流程

• 遍历数组，索引i初始化为0
  • 如果nums[i] = i，说明该值已经和索引相互对应，continue进入下一轮循环
  • 判断nums[i] == nums[nums[i]]，说明索引i和索引num[i]处的值相同，找到重复值，返回num[i]
  • 否则，交换索引i和num[i]处的两个元素，交换时注意把num[i]保存为tmp，下表也要使用tmp
• 遍历后若没有找到，返回-1

复杂度分析：

• 时间复杂度 O(N)： 遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1) 。
• 空间复杂度 O(1)： 使用常数复杂度的额外空间。

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i < nums.length;i++) {
            // 值和索引已经对应
            if(nums[i] == i)
                continue;
            // 找到重复元素
            if(nums[nums[i]] == nums[i])
                return nums[i];
            else {  
                // 交换元素，注意下表也要使用tmp
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }
        // 没有找到
        return -1;
    }
}