剑指 Offer 02 - 10代码题解

剑指 Offer 02 - 10代码题解

这里写目录标题

（1）剑指 Offer 02. 实现Singleton模式（2）剑指 Offer 03题一. 数组中重复的数字

法一：把数组排序，再遍历即可法二：哈希表实现，使用HashSet和add方法,时间空间复杂度均为O（n）法三：优化法二空间复杂度到O（1），略 （2）剑指 Offer 03题二. 不修改数组找出重复的数字

法一：同上HashSet或者辅助数组实现，时间空间复杂度均为O（n）法二：基于二分查找思想实现，时间复杂度O（nlogn），空间复杂度O（1） （3）剑指 Offer 04.（4）剑指 Offer 05.（5）剑指 Offer 06.（6）剑指 Offer 07.（7）剑指 Offer 08.（8）剑指 Offer 09.（9）剑指 Offer 10.一级目录

二级目录

三级目录

（1）剑指 Offer 02. 实现Singleton模式 （2）剑指 Offer 03题一. 数组中重复的数字

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

法一：把数组排序，再遍历即可

排序的话可以使用多种排序算法，也可以直接使用API：Arrays.sort(nums)
出于好奇研究了一下这个API到底调用的是哪种排序算法。
结论：Arrays.sort并不是单一的排序，而是插入排序，快速排序，归并排序三种排序的组合。
具体细节参考：
Java的Arrays.sort()方法到底用的什么排序算法

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

法二：哈希表实现，使用HashSet和add方法,时间空间复杂度均为O（n）

    public int findRepeatNumber(int[] nums) {
        
        Set set = new HashSet();
        int temp = -1;
        for(int num : nums) {
            if(!set.add(num)) {
                temp = num;
            }
        }
        return temp;
    }

法三：优化法二空间复杂度到O（1），略 （2）剑指 Offer 03题二. 不修改数组找出重复的数字 法一：同上HashSet或者辅助数组实现，时间空间复杂度均为O（n） 法二：基于二分查找思想实现，时间复杂度O（nlogn），空间复杂度O（1） （3）剑指 Offer 04. （4）剑指 Offer 05. （5）剑指 Offer 06. （6）剑指 Offer 07. （7）剑指 Offer 08. （8）剑指 Offer 09. （9）剑指 Offer 10. 一级目录 二级目录 三级目录