189 8069 5689

【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://cdxtjz.com/article/pejej.html

其他资讯