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

目录

题目

解题

方法一、直接法

方法二、位运算

题目

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

一个长度为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）数组从1开始，那么答案数是0；2）答案数在数组中，即大于nums[0]且小于nums[nums.size()-1]；3）答案数在数组外，即大于nums[nums.size()-1]。所以直接编码即可，看下边代码。

代码：（C++）

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 int missingNumber(vector<int>& nums) {
     
    
   

    

     

    
    

     
 if (nums[0] == 1) return 0;
     
    
   

    

     

    
    

     
 for(int i = 1; i < nums.size(); i++) {
     
    
   

    

     

    
    

     
 if (nums[i] == nums[i-1] + 1) {
     
    
   

    

     

    
    

     
 continue;
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     
 return nums[i] - 1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return nums.size();
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（n）。

空间复杂度：O（1）。

执行结果：

方法二、位运算

分析：利用位运算异或的特性，两个相同的数异或为0，所以思路就是先遍历 0 ~ n-1 所有数，进行异或运算，然后遍历数组元素，利用上一步骤的结果进行异或运算，本题中不存在的那个数最后就会被剩下，也就是结果。

代码：（C++）

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 int missingNumber(vector<int>& nums) {
     
    
   

    

     

    
    

     
 int n = nums.size();
     
    
   

    

     

    
    

     
 int bit = 0;
     
    
   

    

     

    
    

     
 for (int i = 0; i <= n; i++){
     
    
   

    

     

    
    

     

       bit^=i;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for (int x : nums) {
     
    
   

    

     

    
    

     

       bit^=x;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return bit;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（n）。

空间复杂度：O（1）。

执行结果：

 如果有疑问，欢迎评论留言或者私信沟通！ 

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107924843