Leetcode力扣秋招刷题路-剑指 Offer 03

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

从0开始的秋招刷题路记录下所刷每道题的题解帮助自己回顾总结

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

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

示例 1

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

解法一排序比较相邻数字。时间复杂度O(NlogN)空间复杂度O(1)。

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 1; ++i){
            if(nums[i] == nums[i + 1])
                return nums[i];
        }
        return -1;
    }
}

解法二哈希。时间复杂度O(N)空间复杂度O(N)。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] ans = new int[100001];
        for(int num: nums){
            if(ans[num] == 1)
                return num;
            else
                ans[num] = 1;
        }
        return -1;
    }
}

解法三注意到题干中说明了数组长度为n并且数组中的数字范围都在0到n-1中因此整个数组中若无重复数字则下标为i的数字一定等于i如果有重复的数字则在某些位置上的数字定会重复。根据此规律我们可以遍历整个数组如果下标为i的数字等于i那么继续比较下一个数字如果下标为i的数字不等于i则互换下标为nums[i]和i的数字再继续比较。时间复杂度O(N)空间复杂度O(1)。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int temp;
        int i = 0;
        while(i < nums.length){
            if(nums[i] == i){
                i++;
                continue;
            }
            else{
                if(nums[i] == nums[nums[i]])
                    return nums[i];
                else{
                  // 交换顺序不能错
                    temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        return -1;
    }
}