侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

53-Ⅱ 0~n-1中缺失的数字

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 142 阅读 / 1,204 字 / 正在检测是否收录...

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

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

方法一:二分法

因为数组已经排序好了,可以通过二分法去确定,缺失的是哪一个数字。

根据题意,可以将数组分为两部分:

  • 左子数组:$nums[i] = i$;
  • 右子数组:$nums[i] \neq i$;

缺失的数字应当等于右子数组第一个元素的索引。

代码:

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

复杂度分析

  • 时间复杂度$O(logN)$:二分法为对数级别复杂度。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。

方法二:异或

异或有两条性质:① 0 ^ a = a ; ② a ^ a = 0

因为数组中的数字都是唯一的,将数组内的元素全部进行异或操作,然后在和 $0$ ~ n 进行异或,最后会只剩下那个不在数组中的数字。

public int missingNumber(int[] nums) {
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }
    for (int i = 0; i <= nums.length; i++) {
        xor ^= i;
    }
    return xor;
}

复杂度分析

  • 时间复杂度$O(N)$:算法进行 $2N$ 次循环。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。
0

评论区