【C语言刷题系列】消失的数字

用户11396077

发布于 2024-12-06 18:56:28

8000

代码可运行

文章被收录于专栏：C/C++指南C/C++指南

运行总次数：0

代码可运行

一、问题描述

问题的要点：

数组中存储了0到n的数字，但缺失了一个
数组是无序的
时间复杂度要求 O（n）

二、解题思路

题目要求时间复杂度为O（n） 如果用暴力解法:先将数组排序，再对数组每个元素与相邻元素进行比对的方法，受制于排序的时间复杂度至少为O（nlogn），所以这种方法是行不通的

方法一:求和做差

对时间复杂度优化 先将0到n相加求和，再将数组元素求和，两个结果作差就是缺失的数字 用两个循环求和，时间复杂度为O（n） 该算法可以进一步优化: 0到n求和可以使用等差数列求和的公式（（首项+尾项)*项数/2)，直接求出结果不过时间复杂度已不能进一步降低了

方法二:异或

相加求和的方法，对于数组元素较大的情况，无法正确处理 这里使用异或的方法来解决—— 将数组每个元素异或一遍，再跟0到n依次异或，得到的结果就是缺失的数字 （原理是任意两个相同的数字异或，结果为0；0与任何数字异或，结果是该数字本身） 时间复杂度为O（n）

三、C语言代码实现

方法一实现：

int missingNumber1(int* nums, int numsSize)
{
    int sum1 = (0 + numsSize) * (numsSize + 1) / 2;//0到numsSize求和
    int sum2 = 0;
    for (int i = 0; i < numsSize; i++)//数组求和
    {
        sum2 += nums[i];
    }
    return sum1 - sum2;//做差
}

方法二实现：

int missingNumber2(int* nums, int numsSize)
{
    int ret = 0;
    for (int i = 0; i <= numsSize; i++)//与0到numsSize异或
    {
        ret ^= i;
    }
    for (int i = 0; i < numsSize; i++)//与数组每个元素异或
    {
        ret ^= nums[i];
    }
    return ret;
}

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

原始发表：2024-12-06，如有侵权请联系 cloudcommunity@tencent.com 删除

排序