Leetcode—Day4—剑指offer 03+53 （查找算法）

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

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

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

​​​​​​剑指 Offer 53 - I. 在排序数组中查找数字 I 简单

统计一个数字在排序数组中出现的次数。

计算次数第一反应HashMap，但是这里说明是排序数组，所以可以通过二分查找找到target，然后向前向后查找target并记录次数

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length-1;
        if(low==high) return nums[0]==target?1:0;
        while(low<=high){
            int mid = (low+high)/2;
            if(targetnums[mid]) low = mid+1;
            else{
                int ans = 1 , i = mid;
                while(--i>=0 && nums[i]==target) ans++;
                i=mid;
                while(++i 
剑指 Offer 53 - II. 0～n-1中缺失的数字 简单
 
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 
本题：1. 递增排序 ； 2. 所有数字都是 0 ~ n-1 ；可以通过二分查找定位数字，如果nums[mid]==mid，说明mid以及之前的数字都在正确的位置上，缺少的数字在mid之后；否则说明缺少的数字在mid之前
class Solution {
    public int missingNumber(int[] nums) {
        int low = 0 ,high = nums.length-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(nums[mid]==mid) low = mid+1;
            else high = mid-1;
        }
        return low;
    }
}