数组-寻找数组中缺少的数字

十二月 21, 2021 2232

        每日一题，提升自己。今天分享一道关于寻找数组中缺少的数字的题目，且听我细细道来。

数组 - 寻找数组中缺少的数字

1. 题目描述

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

示例：

示例1：

输入：[0,1,3]

输出：2

示例2：

输入：[0,1,2,3,4,5,6,7,9]

输出：8

提示：

1 <= 数组长度 <= 10000

2. 解题思路

2.1 思路一

        本题给的数组数字范围都是在0~n-1之间的，那么很容易想到的就是比较当前数字和当前在数组内的角标是否相同，因为如果不缺数字的话数组的内容是和角标一一对应的。所以在遍历数组时，如果当前数字和角标不同，那么则证明当前角标对应的数字缺失，返回即可。

2.2 思路二

本题数组内的数数字如果不缺少的话，是一个连续的数组，那么可以通过前后两个数之差来判断是否缺少。顺序情况下差值应该是1，所以当差值大于1，则表示缺少数字，缺少的是前一个数加一。

2.3 思路三

本题给的数组既然是一个顺序递增的，同样也是查找数字，那么就可以用二分法来处理。因为数组从0增序存储，所以如果不确实则数组数字与数组索引相对应。缺失的部分等于“右子数组的首位元素”。

  • 左子数组：nums[i] == i，数字与数组索引相等，则前半部分没有缺失，在右半部分查找。
  • 右子数字：nums[i] != i，数字与数组索引不相等，则缺失数字在左半部分。

复杂度：

  • 时间复杂度：O(logn)。
  • 空间复杂度：O(1)。

3. 算法流程

3.1 思路一流程

  1. 遍历数组，比较当前数字和当前索引。
  2. 如果当前数字和索引不相等，则返回当前索引。

3.2 思路二流程

  1. 如果第一个数不等于0，则代表缺少0，返回0。
  2. 否则初始化当前数字pre=nums[0]。
  3. 从第二位开始遍历数组，遍历的当前数与pre差值大于1，则代表缺失数为pre+1。
  4. 如果当前数与pre差值不大于1，pre等于当前数，继续遍历。

3.3 思路三流程

  1. 首先初始化二分查找的左边界left = 0和右边界right = nums.length-1。
  2. 当左边界不大于右边界时进行查找。
  3. 计算中间位置mid = (left + right) / 2。
  4. 如果 nums[mid] == mid ，则缺失的元素，即右子数组的首位元素在 [mid + 1, right] 中间，令 left = mid + 1。
  5. 如果 nums[mid] != mid ，则缺失的元素，即右子数组的首位元素在 [left, mid - 1] 中间，令 right = mid - 1。

4. 代码实现

4.1 思路一代码

Java代码实现如下：

1
2
3
4
5
6
7
8
public static int missingNumber(int[] nums){
    for (int i=0;i<nums.length;i++){
        if (nums[i] != i){
            return i;
        }
    }
    return nums.length;
}

4.2 思路二代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int missingNumber(int[] nums){
    if (nums[0] != 0){
        return 0;
    }
    int pre = nums[0];
    for (int i=1;i<nums.length;i++){
        if (nums[i] - pre > 1){
            return pre+1;
        }
        pre = nums[i];
    }
    return nums.length;
}

4.3 思路三代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
public static int missingNumber(int[] nums){
    int left=0,right=nums.length-1;
    while (left < right){
        int mid = (left + right) / 2;
        if (nums[mid] == mid){
            left = mid + 1;
        }else {
            right = mid - 1;
        }
    }
    return left;
}