leetcode 287

寻找重复数

Posted by Static on May 26, 2020

题目链接:https://leetcode-cn.com/problems/find-the-duplicate-number/

题目描述


分析

1. 嵌套for循环

2. 利用map查重


代码实现

public enum Q287 {
    instance;
    public int findDuplicate(int[] nums) {
        if(nums.length<=1) return 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            Integer count = map.get(num);
            if(count==null){
                map.put(num,1);
            }else{
                return num;
            }
        }
        return 0;
    }
    public int findDuplicate1(int[] nums) {
        int l=nums.length;
        for(int i=0;i<l;i++){
            for(int j=i+1;j<l;j++){
                if(nums[i]==nums[j]){
                    return nums[i];
                }
            }
        }
        return 0;
    }

    // LeetCode 解法
    public int findDuplicate2(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }


    public static void main(String[] args) {
        // assert 1
        System.out.println(Q287.instance.findDuplicate1(new int[]{1,1,3,4,5}));
        // assert 3
        System.out.println(Q287.instance.findDuplicate1(new int[]{1,2,3,4,3}));
        // assert 0
        System.out.println(Q287.instance.findDuplicate1(new int[]{1,2,3,4,5}));
        // assert 4
        System.out.println(Q287.instance.findDuplicate2(new int[]{1,2,3,4,4}));
    }
}