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

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

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

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

限制：
2 <= n <= 100000

解题思路

1）hashmap的解法很容易想到，这里不再赘述
2）认真审题，题意中说明了，数组元素必定在0~n-1的范围内 遍历nums数组，对比每个位置元素，是否是当前位置的元素，即是否满足nums[i] == i

import java.util.HashSet;

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 认真审题，题意中说明了，数组元素必定在0~n-1的范围内 遍历nums数组
        // 对比每个位置元素，是否是当前位置的元素，即是否满足nums[i] == i
        for (int i = 0; i < nums.length; i++) {
            // 如果不满足，则将nums[i]换到nums[nums[i]]位置去
            if (nums[i] != i) {
                while (nums[i] != i) {
                    // 如果此时nums[i] == nums[nums[i]]，则为重复元素
                    if (nums[nums[i]] == nums[i]) {
                        return nums[i];
                    } else {
                        int temp = nums[nums[i]];
                        nums[nums[i]] = nums[i];
                        nums[i] = temp;
                    }
                }
            }
            // 如果满足，则继续遍历下一个元素
        }
        return -1;
    }
}