题目描述

image.png

解题思路

哈希表

  1. /**
  2.          * 哈希表
  3.          *
  4.          * @param nums
  5.          * @return
  6.          */
  7. public int missingNumber(int[] nums) {
  8.     int[] array = new int[nums.length + 1];
  9.     for (int i = 0; i < nums.length; i++) {
  10.         array[nums[i]] = 1;
  11.     }
  13.     int result = 0;
  15.     for (int i = 0; i < array.length; i++) {
  16.         if (array[i] != 1) {
  17.             result = i;
  18.             break;
  19.         }
  20.     }
  22.     return result;
  23. }

二分法

排序数组中的搜索问题，首先想到 二分法 解决。根据题意，数组可以按照以下规则划分为两部分。

  • 左子数组： nums[i] = i;
  • 右子数组： nums[i] 不等于 i;

缺失的数字等于 “右子数组的首位元素” 对应的索引；因此考虑使用二分法查找 “右子数组的首位元素” 。
image.png

算法解析：

  • 初始化： 左边界 i = 0，右边界 j = len(nums) - 1；代表闭区间 [i, j]。
  • 循环二分： 当 i≤j 时循环 （即当闭区间 [i, j] 为空时跳出） ；
    • 计算中点 m = (i + j) / 2
    • 若 nums[m] = m ，则 “右子数组的首位元素” 一定在闭区间 [m + 1, j] 中，因此执行 i = m + 1；
    • 若 nums[m] 不等于 m，则 “左子数组的末位元素” 一定在闭区间 [i, m - 1]中，因此执行 j = m - 1；

返回值： 跳出时，变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可。

  1. /**
  2.          * 二分查找
  3.          *  时间复杂度 O(log N)： 二分法为对数级别复杂度。
  4.          * 空间复杂度 O(1)： 几个变量使用常数大小的额外空间。
  5.          * @param nums
  6.          * @return
  7.          */
  8. public int missingNumber(int[] nums) {
  9.     int left = 0;
  10.     int right = nums.length - 1;
  11.     while (left <= right) {
  12.         int mid = (right - left) / 2;
  13.         if (nums[mid] == mid) { // 是否等于索引
  14.             left = mid + 1;
  15.         } else right = mid - 1;
  16.     }
  18.     return nums[left];
  19. }

复杂度分析：
  • 时间复杂度 O(\log N)O(logN)： 二分法为对数级别复杂度。
  • 空间复杂度 O(1)O(1)： 几个变量使用常数大小的额外空间。