【力扣】268.丢失的数字

简介: 【力扣】268.丢失的数字

题目描述

给定一个包含 [0, n]n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1:

输入:nums = [3,0,1]

输出:2

解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:

输入:nums = [0,1]

输出:2

解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]

输出:8

解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

示例 4:

输入:nums = [0]

输出:1

解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

提示:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

解题方法

  • C 排序法
/* 自定义比较函数 */
int mycmp(int* a, int* b) { return *a - *b; }

int missingNumber(int* nums, int numsSize) {
    /* 由小到大排序 */
    qsort(nums, numsSize, sizeof(int), mycmp);
    /* 遍历数组 索引与值对应不上的即为缺失的元素*/
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    return numsSize;
}
  • C 求和法
int missingNumber(int* nums, int numsSize) {
    /* 求 1 + 2 + 3 + .... + numsSize 的和 */
    int sum = numsSize * (numsSize + 1) / 2;
    for (int i = 0; i < numsSize; i++) {
        /* 依次减去数组元素,剩下的即是丢失元素 */
        sum = sum - nums[i];
    }
    return sum;
}



相关文章
|
9月前
|
数据采集 Web App开发 监控
Python爬虫:爱奇艺榜单数据的实时监控
Python爬虫:爱奇艺榜单数据的实时监控
|
存储 弹性计算 运维
如何使用Argo Workflows编排基因计算工作流?
为了高效、准确地整合和分析大量基因计算数据,工作流的自动化编排成为了一项关键技术,而容器化、灵活、易用的工作流引擎Argo Workflows在其中脱颖而出,成为串联基因计算各个环节的得力助手。
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
分布式计算 DataWorks 关系型数据库
DataWorks常见问题之删除odps中表的历史分区失败如何解决
DataWorks是阿里云提供的一站式大数据开发与管理平台,支持数据集成、数据开发、数据治理等功能;在本汇总中,我们梳理了DataWorks产品在使用过程中经常遇到的问题及解答,以助用户在数据处理和分析工作中提高效率,降低难度。
|
数据采集 机器学习/深度学习 数据可视化
python——pycharm进行统计建模
python——pycharm进行统计建模
244 0
|
机器学习/深度学习 人工智能 算法
算法金 | 这绝对是不一样的,独一无二的逻辑回归算法体验
算法导师“算法金”分享了更新的AI课件,邀请读者找错并提建议,采纳者可免费参与其付费专栏内测并获赠两份成品。文中提供了多张相关图片,但未直接展示具体内容。读者可通过链接参与互动,助力完善内容。
72 3
算法金 | 这绝对是不一样的,独一无二的逻辑回归算法体验
|
自然语言处理 Python
在python中词袋模型
在python中词袋模型
218 6
|
算法 数据挖掘 大数据
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
|
算法 索引
【力扣】35. 搜索插入位置
【力扣】35. 搜索插入位置
|
SQL
leetcode-SQL-1731. 每位经理的下属员工数量
leetcode-SQL-1731. 每位经理的下属员工数量
105 0

热门文章

最新文章