剑指Offer03. 数组中重复的数字【简单】

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

题目描述：

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

JAVA代码

普通方法

两层遍历挨个寻找第一个重复的数字。

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

Map方法

使用map存储nums数据，以nums的值作为map的key，当遇到相同的key值时返回该数值。

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i<nums.length;i++){
    
            if(map.containsKey(nums[i])){
    
                return nums[i];
            }
            map.put(nums[i],i);
        }
        return -1;
    }
}

官方方法

使用Set，仅存储一个值，比Map方法存储两个值更加简便
拓展：Set无序的不可重复的。add()方法返回false，则说明存在重复的值。

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Set<Integer> set = new HashSet<Integer>();
        int result = -1;
        for(int num:nums){
    
            if(!set.add(num)){
    
                result = num;
                break;
            }
        }
        return result;
    }
}

“这里没有涉及到其他复杂的关于位置的操作，所以仅仅存储值就足够了。”