【C语言】LeetCode面试题17.04.消失的数字的n种解法-创新互联

本文涉及的库函数或者数据结构与算法不熟悉的地方，可以在文章末找到相关知识详解链接。

创新互联公司-专业网站定制、快速模板网站建设、高性价比方山网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式方山网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖方山地区。费用合理售后完善，10年实体公司更值得信赖。文章目录

• 题目描述
• 解法一
• • 题解代码
• 解法二
• • 题解代码
• 解法三
• • 题解代码
• 解法四
• • 题解代码
• 总结

题目描述

OJ链接：LeetCode 面试题 17.04. 消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

解法一

题目中描述，数组nums包含从0到n的所有整数，但缺少了其中一个。
那么我们可以通过等差数列求和公式，或者0-n循环求和，都可以得到总和totalNum。我们只需要再遍历减去数组的各个元素，剩下的值就是消失的数字了。
时间复杂度O(n)，空间复杂度O(1)。

题解代码

//nums是题目给我们的数组，numsSize是数组的大小
int missingNumber(int *nums, int numsSize)
{//等差数列求和公式 项数*（首项+尾项）/2
	//我们要求0-n，有n+1项，首项为0，尾项为n，numsSize大小是n
	int totalNum = (numsSize + 1) * (0 + numsSize) / 2;

	//遍历减去已有数
	for (int i = 0; i< numsSize; i++)
		totalNum -= nums[i];

	//此时返回值totalNum就是missingNum
    return totalNum;
}//timeO(n) spaceO(1)

解法二

我们知道异或^位运算符（二进制位相同为0，相异为1）有这样的性质：

• 数字与自己本身异或为0，5^5=0
• 数字与0异或还是自己本身，7^0=7，0二进制位全是0，和0相同的就是0，相异的就是1，不变

所以我们可以定义个数字Num=0，然后让他与0-n各个数字遍历异或，再把他与nums各个元素异或，存在的数字就会异或两遍得0，不会对Num造成影响，最后只有落单的消失的数字，与Num=0异或，是Num值变为消失的数字值。
时间复杂度O(n)，空间复杂度O(1)。

题解代码

int missingNumber(int *nums, int numsSize)
{//从0-n遍历异或一遍
    int Num = 0;
    for (int i = 0; i<= numsSize; i++)
        Num ^= i;

    //再把nums各个元素异或一遍
    for (int i = 0; i< numsSize; i++)
        Num ^= nums[i];

    //此时的Num的值就是missingNum
    return Num;
}//timeO(n) spaceO(1)

解法三

nums是0-n中消失了一个数的数组，如果我们自定义一个n+1大小的数组arr并赋值为0，用nums各个元素做下标，如果数字存在，则把数组arr对应位置下标元素赋值为1，再遍历一次查找哪个下标值为0，就找到消失的数字了。
时间复杂度O(n)，空间复杂度O(n)

题解代码

int missingNumber(int *nums, int numsSize)
{//开辟一个n+1大的数组，并赋值为0
    int *arr = (int *)malloc((numsSize + 1) * sizeof(int));
    memset(arr,0, (numsSize + 1) * sizeof(int));

    //数字存在则把对应数组下标位置赋值为1
    for (int i = 0; i< numsSize; i++)
        arr[nums[i]] = 1;

    //当arr值为0会停止循环，此时的值就是消失的数字
    int missNum = 0;
    while (arr[missNum])
        missNum++;

    return missNum;
}//timeO(n) spaceO(n)

解法四

我们还可以把数组进行快速排序，再从0开始用二分查找法遍历查找数字是否存在。
快速排序时间复杂度O(nlogn)，空间复杂度O(logn)。
二分查找时间复杂度O(logn)，空间复杂度O(1)。
所以此题解时间复杂度O(nlogn)，空间复杂度O(logn)。
代码可能跑不过OJ会挂。

题解代码

int int_cmp(const void *e1, const void *e2)
{return *(int *)e1 - *(int *)e2;
}

int missingNumber(int *nums, int numsSize)
{//先将数组快排
    qsort(nums, numsSize, sizeof(int), int_cmp);

    //从0-n逐个数字二分查找, 没查找到的数字就是
    //flag用来标记数字是否查找到
    int flag = 0;
    int begin = 0;
    int end = numsSize - 1;
    int mid = (begin + end) / 2;
    int missNum = 0;
    for (missNum = 0; missNum<= numsSize; missNum++)
    {//二分查找
        while (begin<= end)
        {if (nums[mid] >missNum)
            {end = mid - 1;
            }
            else if (nums[mid]< missNum)
            {begin = mid + 1;
            }
            else
            {flag = 1;
                break;
            }
            mid = (begin + end) / 2;
        }

        //没有查找到，终止for循环
        if (!flag)
        {break;
        }
        //查找到了，初始化二分查找的基本变量，进入下次循环
        else
        { begin = 0;
             end = numsSize - 1;
             mid = (begin + end) / 2;
             flag = 0;
        } 
    }

    return missNum;   
}//timeO(nlogn) spaceO(logn)

总结

解法一简单易想，时间复杂度和空间复杂度都最佳。
解法二巧妙利用了位运算异或^的特性，十分巧妙，时间和空间复杂度也很佳，也是本文主要想介绍的解法。
解法三利用数组下标和对应元素值的映射，解法也不错。
解法四暴力的遍历查找，可以解决问题，但时间复杂度太高。

---

memset内存赋值函数详解
qsort快速排序函数详解

---

码字不容易，欢迎关注，点赞，收藏，评论，转发。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页名称：【C语言】LeetCode面试题17.04.消失的数字的n种解法-创新互联
当前路径：http://kswsj.com/article/pejej.html