剑指offer-day04查找算法

1.数组中重复的数

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

解法1：原地交换

解题思路：

1. 遍历数组 nums ，设索引初始值为 i = 0i=0 :
2. 若 nums[i] = inums[i]=i ： 说明此数字已在对应索引位置，无需交换，因此跳过；
3. 若 nums[nums[i]] = nums[i] ： 代表索引 nums[i] 处和索引 i 处的元素值都为nums[i] ，即找到一组重复值，返回此值 nums[i]nums[i] ；否则： 交换索引为 nums[i] 的元素值，将此数字交换至对应索引位置。
4. 若遍历完毕尚未返回，则返回 -1 。

public int findRepeatNumber(int[] nums) {
        for(int i=0;i<nums.length;i++) {
			while(nums[i]!=i) {
				if(nums[nums[i]]==nums[i])
					return nums[i];
				else {
					nums[i]=nums[i]^nums[nums[i]];
					nums[nums[i]]=nums[i]^nums[nums[i]];	
					nums[i]=nums[i]^nums[nums[i]];
				}
			}
		}
		return -1;
    }

解法2：哈希表

解题思路：
利用hashset不可重复特性，遇到set集合中存在的元素，直接返回

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

2.在排序数组中查找一个数

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

解法1：计数器

解题思路：
定义计数器count，遍历更新count，返回

 public int search(int[] nums, int target) {
        int count=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==target){
                count++;
            }
            if(nums[i]>target){
                return count;
            }
        }
        return count;
    }

解法2：二分法

解题思路：

1. 用二分法找到等于给定值的左边界
2. 从左边界遍历到第一个大于给定值的位置，count累加
3. 返回count

public int search(int[] nums, int target) {
        int left =0,right = nums.length-1;
        int count = 0;
        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]>=target)
                right=mid;
            if(nums[mid]<target)
                left = mid+1;
        }
        while(left<nums.length&&nums[left++]==target)
            count++;
        return count;
    }

3.0~n-1范围上缺失的数

解法1：遍历大法

解题思路：
直接从头开始遍历，直到找到第一个索引和值不匹配的索引

boolean flag=true;
        for (int i = 0; i < nums.length; i++) {
            nums[i]=nums[i]^i;
            if(nums[i]!=0){
                flag=false;
                return i;
            }
        }
        if(flag){
            return nums.length;
        }
        return 0;

解法2：二分法

解题思路:
利用二分法，加速寻找

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