C语言练习之消失的数字（两种解法）

目录

前言

一、思路

思路一（异或法）

思路二（求和法）

二、代码

代码1

代码2

总结

---

前言

题目描述：

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

测试举例：

输入：[3,0,1]
输出：2

一、思路

思路一（异或法）

首先要明白什么是异或（异或就是二进制位的数值，相等则为0，不相等则为1）

假设a!=b，则有以下公式：

a^a = 0;

a^b = b^a;

0^a = a;

根据公式可以想到：

先将0~n的所有数字全部异或

ret1 = 0^1^……^n;

再将数组（缺失数字）中的数全部异或

ret2 = nums[0]^nums[2]^……^nums[numsSize-1];

最后将ret1和ret2异或，所得结果就是缺失的数字。

思路二（求和法）

由观察可知，缺少的数字等于0~n数字之和减去0~n除了所缺少数字外其他数字之和。

二、代码

为了方便大家的交流和学习，我将函数的代码放置在下方。

代码1

  

   

    

     

    
    

     

      int missingNumber(int* nums, int numsSize){
     
    
   

    

     

    
    

     
    
      int i = 
      0;
     
    
   

    

     

    
    

     
    
      int sum1 = 
      0,sum2 = 
      0;
     
    
   

    

     

    
    

     
    
      for(i = 
      0;i < numsSize +
      1; i++)
      //0~n个整数之和
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              sum1 += i;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      for(i = 
      0; i < numsSize ;i++)
      //所给数组的元素之和
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              sum2 += nums[i];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return sum1 - sum2;
     
    
   

    

     

    
    

     

      }
     
    
  

代码2

  

   

    

     

    
    

     

      int missingNumber(int* nums, int numsSize){
     
    
   

    

     

    
    

     
    
      int i = 
      0;
     
    
   

    

     

    
    

     
    
      int ret1 = 
      0,ret2 = 
      0;
     
    
   

    

     

    
    

     
    
      for(i = 
      0;i < numsSize +
      1; i++)
      //0~n所有整数的异或
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              ret1 ^= i;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      for(i = 
      0; i < numsSize ;i++)
      //所给数组的所有元素的异或
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              ret2 ^= nums[i];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return ret1^ret2;
     
    
   

    

     

    
    

     

      }
     
    
  

---

总结

以上就是今天要讲的内容，本文简单的介绍了如何用C语言解决消失的数字这个题的思路。

这个题是我在做题时遇到的一道觉得很有意思的题，对我的做题思路有很大的启发作用，所以将它分享给大家。

如果本篇文章对你有所启发的话，希望可以支持支持作者，后续作者也会定期更新学习记录。谢谢大家！

转载：https://blog.csdn.net/xjjxjy_2021/article/details/127929967