[数据结构与算法]剑指 offer java day04

T1 03. 数组中重复的数字

双重循环

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

krahets 大佬的原地交换 。对题干深度理解，不重复时索引和数应是一对一

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 temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }
}

T2 53 - I. 在排序数组中查找数字 I

排序数组 二分法

class Solution {
    public int search(int[] nums, int target) {
        //升序数组 目标-1的右边界就是目标的左边界
        return border(nums,target) - border(nums,target-1);
    }
    //寻找目标数的右边界
    int border(int[] nums,int target){
        int i=0,j = nums.length-1;
        while(i<=j){
            int m =(i+j)/2;
            if(nums[m]<=target) i=m+1;
            else j = m-1;
        }
        return i;
    }
}

T3 53 - II. 0～n-1中缺失的数字

class Solution {
    public int missingNumber(int[] nums) {
        int i=0,j=nums.length-1;
        while(i<=j){
            int m= (i+j)/2;
            if(nums[m]==m) i=m+1;
            else j=m-1;
        }
        return i;
    }
}