0~n-1中缺失的数字(剑指offer 53-II)

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

一、题目描述



一个长度为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


二、思路讲解



1、方法一

     

对于我这个算法小白来说,每次看见查找的题总要试试能不能暴力破解,这次成功了。

     

因为数组是递增的,索引和值对应不上,则必然缺失了;若全对上了,则必然缺失了n。


2、方法二

     

一说到查找,首选应该是二分查找。

     

承接上面的思路,如果二分位置的索引等于值,那么左边都不用查了,直接将右边作为子数组,继续二分即可;如果二分位置的索引不等于值,则将右边的指针左移一位,继续二分。直至两指针相遇,返回i指针对应的值即可。


三、算法描述



1、方法一


遍历数组nums,若索引与值不同,则返回索引;若能够走出循环,则必然数组里面必然是0~n-1的情况,则直接返回n        


四、Java代码实现



1、方法一


class Solution {
  public static int missingNumber(int[] nums) {
    //遍历数组
    for(int i=0; i<nums.length; i++) {
      //因为数组为递增数组,所以若索引小于它对应的值,则说明缺失了这个索引本该对应的数字
      if(i < nums[i]) {
        return i;
      }
    }
    //考虑[0]、[0,1]、[0,1,2]……的情况
    return nums.length;
    }
}


2、方法二


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


五、时空复杂度分析



1、方法一

     

时间复杂度:O(n)        遍历数组一次

     

空间复杂度:O(1)


2、方法二

     

时间复杂度:O(logn)        二分查找

     

空间复杂度:O(1)



相关文章
|
8月前
剑指Offer LeetCode 面试题53 - II. 0~n-1中缺失的数字
剑指Offer LeetCode 面试题53 - II. 0~n-1中缺失的数字
36 0
剑指offer-1.找出数组中重复的数字
剑指offer-1.找出数组中重复的数字
35 0
|
算法 Java
【算法题目解析】杨氏矩阵数字查找
一道面试时可能遇到的算法问题,杨氏矩阵。可以重点关注思考方式,而不是死记硬背。
45 0
|
算法 C语言
【基础算法】浅浅刷个小题 # 移动零 # 丢失的数字 # 转换成小写字母 # 和为零的N个不同整数 # 猜数字 #
【基础算法】浅浅刷个小题 # 移动零 # 丢失的数字 # 转换成小写字母 # 和为零的N个不同整数 # 猜数字 #
剑指offer 56. 0到n-1中缺失的数字
剑指offer 56. 0到n-1中缺失的数字
71 0
leetcode剑指offer53–n-1中缺失的数字(二分//or等差数列)
leetcode剑指offer53–n-1中缺失的数字(二分//or等差数列)
力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数
力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数
159 0
力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数
牛客网——序列中删除指定数字
牛客网——序列中删除指定数字
133 0
牛客网——序列中删除指定数字
亲身经历:如何判断一个字符在a/z之前?
亲身经历:如何判断一个字符在a/z之前?
70 0
AcWing 68. 0到n-1中缺失的数字
AcWing 68. 0到n-1中缺失的数字
77 0
AcWing 68. 0到n-1中缺失的数字