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

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

使用辅助Map

写法一：

public class Solution {
    public int findRepeatNumber(int[] nums) {
        // map记录元素是否出现
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            // 如果存在，说明重复，直接返回结果
            if (map.containsKey(num)) {
                return num;
            } 
            // 如果不存在，放入map
            else {
                map.put(num, 1);
            }
        }
        return -1;
    }
}

写法二：

class Solution {
    public int findRepeatNumber(int[] nums) {
        // map记录元素出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        // 将元素依次放入map
        Arrays.stream(nums).forEach(e -> map.put(e, map.getOrDefault(e, 0) + 1));
        // 找到出现次数大于1次的元素
        List<Integer> collect = map.entrySet().stream()
                .filter(e -> e.getValue() > 1)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
        // 返回第一个即可
        return collect.get(0);
    }
}

排序再遍历前一元素与后一个元素

public class Solution {
    // 排序后再遍历，如果前一个元素等于后一个元素则返回
    public int findRepeatNumber(int[] nums) {

        if (nums.length == 0) return -1;

        Arrays.sort(nums);
        int pre = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (pre == nums[i]) return pre;
            else pre = nums[i];
        }
        return -1;
    }
}

原地置换

题目说了在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内说明一个数组的一个索引只对应一个元素，并且索引值就等于元素的值，使用调换元素顺序的方式让元素落在自己所属的位置，调换位置之前判断目标位置是否存在该值，如果存在说明该元素重复

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

                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        return -1;
    }
}