LeetCode---消失的数字---C语言实现

小李很执着

发布于 2024-06-15 08:25:18

1690

文章被收录于专栏：学习笔记学习笔记

🐷OJ链接：🐷力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。

你有办法在O(n)时间内完成吗？

注意：本题相对书上原题稍作改动

示例 1：

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

示例 2：

输入：[9,6,4,2,3,5,7,0,1] 输出：8

🐢思路 1：冒泡遍历🐢

1.冒泡排序

2.遍历，如果当前值+1，不等于下一个数字就是下一个数

此时时复杂度为O(N^2)

int missingNumber(int* nums, int numsSize)
{
	int cout=0,temp = 0,i;
	for (i = 0; i < numsSize-1; i++)
	{
		for (int j = 0; j < numsSize -1- i; j++)
		{
			if (nums[j] > nums[j+1])
			{
				temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
				cout = 1;
		    }
		}
		if (cout == 0)
			break;
	}
	for (i = 0; i < numsSize-1; i++)
	{
		if ((nums[i] + 1) != nums[i + 1])
		{
			return nums[i] + 1;
		}
	}
}

🦒思路 2：单身狗异或思想:🦒

res = res ^ x ^ x。对同一个值异或两次，那么结果等于它本身

例如：输入：[9,6,4,2,3,5,7,0,1] 输出：8

我们重新创建一个数组[0.1.2.3.4.5.6.7.8.9]与所求数组[9,6,4,2,3,5,7,0,1]进行异或，

剩下的数字就是缺失的整数。 F(N)=2N-1;

时间复杂度为O(N).

int missingNumber(int* nums, int numsSize)
{
   int ret=0;
   for(int i=0;i<numsSize;i++)
   {
       ret^=nums[i];
   } 
      for(int i=0;i<=numsSize;i++)    
      {
          ret^=i;
      }
      return ret;

🦋思路 3：和差法🦋

1.0—n 等差数列计算和；

2.依次减掉数据中的值，剩下的就是消失的数字.F(N)=N-1

时间复杂度为O(N).

int missingNumber(int* nums, int numsSize)
{
 
    int N=numsSize;
    int sum=((0+N)*(N+1))/2;
    for (int i=0;i<numsSize;i++)
{
    sum-=nums[i];
}
    return sum;
 
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-11-01，如有侵权请联系 cloudcommunity@tencent.com 删除

int