【剑指offer第四天】查找算法

﹏ヽ暗。殇╰゛Y 2022-09-03 14:13 158阅读 0赞

# 第一题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]  
方法一 使用map，注意map在定义时需使用引用类型，不能使用基本类型要使用封装类型  
![在这里插入图片描述][2a4bd571425c4bde9a150a4bc442d896.png]

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

方法二 使用集合

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

方法三 因为题目规定数组中的数是在0-n-1，因此借助数组

class Solution { 
        public int findRepeatNumber(int[] nums) { 
            int []tmp = new int[nums.length];
            for(int i:nums){ 
                tmp[i]++;
                if(tmp[i]>1){ 
                    return i;
                }
            }
            return -1;
        }
    }

原地操作

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

# 题目二 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]  
有序数组中查找出现次数，考虑二分查找，确定左边第一个target的位置是在left处。

class Solution { 
        public int search(int[] nums, int target) { 
            int r = nums.length, l = 0;
            while(l < r){ 
                int mid = (l+r)/2;
                if(nums[mid]<target){ 
                    l = mid + 1;
                }else{ 
                    r = mid;
                }
            }
            int res = 0;
            while(l < nums.length&&nums[l++]==target){ 
                res++;
            }
            return res;
        }
    }

# 题目三 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 2]  
方法一 借助辅助数组

class Solution { 
        public int missingNumber(int[] nums) { 
            int []arr = new int[nums.length+1];
            for(int i:nums){ 
                arr[i]++;
            }
            for(int i = 0;i<=nums.length;i++){ 
                if(arr[i]!=1){ 
                    return i;
                }
            }
            return -1;
        }
    }

方法二 排序数组考虑使用二分查找

> 二分查找时，如果right设置的是nums.length那么while循环中判断没有等于号  
> 如果设置为nums.length-1，循环中的判断需要加上等号

class Solution { 
        public int missingNumber(int[] nums) { 
            int left = 0,right = nums.length;
            while(left < right){ 
                int mid = (left + right)/2;
                if(nums[mid] == mid){ 
                    left = mid + 1;
                }else{ 
                    right = mid;
                }
            }
            return left;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: /images/20220829/013e6a39a611400ab9f1d8c5d084be47.png
[2a4bd571425c4bde9a150a4bc442d896.png]: /images/20220829/2c38c069c9de40e99d10dd94e72f9226.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/331ccc8715414bf398aa9cc8b178ad31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/6e8cacbf5c304f46a1b315f8ba8348a0.png