「剑指Offer」Day04：查找算法（简单）

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

题目描述

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

输入： [2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

方法一：哈希法

class Solution {
    public int findRepeatNumber(int[] nums) { //哈希法
        Set<Integer> set = new HashSet<>();
        int res = -1;
        for(int num : nums){
            if(set.contains(num)){
                res = num;
                break;
            }
            set.add(num);
        }
        return res;
    }
}

方法二：排序法

class Solution {
    public int findRepeatNumber(int[] nums) { //排序法
        Arrays.sort(nums);
        int res = -1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1]){
                res = nums[i];
                break;
            }
        }
        return res;
    }
}

方法三：原地交换

根据题目给出的条件：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。

因此可通过遍历交换建立元素值与下标之间的映射，如下标2的位置存储2，若再次出现2，判断下标2的位置是否已存在元素2，已存在就返回，否则就交换到该位置

若 nums[i] == i ：说明此数字已在对应索引位置，无需交换，直接跳过，只有 nums[i] == i 的时候 i 才递增，这样保证找到相同元素前不会漏掉某些元素的处理；
若 nums[nums[i]] == nums[i] ：代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i] ；
否则：交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。

题解链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/

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

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

题目描述

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

输入: nums = [5,7,7,8,8,10], target = 8

输出: 2

思路

二分查找，在找到了一个目标值之后继续以其为中点往前或往后进行目标值的搜索，以此找到目标值出现的第一个和最后一个位置，通过边界求出现次数，但要注意边界都为0的情况

相似题目：

34. 在排序数组中查找元素的第一个和最后一个位置：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

实现代码

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0){
            return 0;
        }
        int lb = binarySearch(nums, target, true); //确定目标值左边界
        int rb = binarySearch(nums, target, false); //确定右边界
        if(lb == 0 && rb == 0){ //都为0时，可能不存在，也可能目标值在第一个位置
            if(nums[0] == target){
                return 1;
            }else{
                return 0;
            }
        }
        return rb - lb + 1;
    }
    public int binarySearch(int[] nums, int target, boolean leftOrRight){
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int border = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                border = mid;
                if(leftOrRight){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return border;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

输入: [0,1,3]
输出: 2

题目链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof

思路

注意题目条件：递增且n-1个数字的范围为0～n-1，所以可以通过判断元素值是否与对应下标值相等，得到缺失的数字，若不缺失返回数字n-1，即给定数组的长度

实现代码

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