每日一题——找到消失的数字

这篇具有很好参考价值的文章主要介绍了每日一题——找到消失的数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

找到消失的数字

题目链接

每日一题——找到消失的数字,每日一题,# 数组相关,算法,c语言,leetcode

思路

一个长度为n的数组中所有数据的范围在[1,n]内,题目要求我们找出在[1,n]范围内,但数组中没有出现的数字

如果可以使用额外空间,那这题就好办了。我们直接创建一个相同大小的数组,数组的每个位置代表[1,n]的每个元素,然后遍历数组计数就行。

我们这里主要讲不利用额外空间,直接在原数组原地修改的方法法。文章来源地址https://www.toymoban.com/news/detail-615557.html

  • 我们先来看一个长度为n,数据范围在[1,n]内,且没有数字消失的数组[1,2,3,4,5],那么,我们可以发现,可以利用这些数据的绝对值减一当作下标,使数组的每个位置都变为负数[-1,-2,-3,-4,-5]
  • 那么再进一步想,如果数组中缺少了[1,n]中的某一个元素,那么数组当中一定有一个位置的数据不会被置为负数,而这个位置的下标加一,就是我们要找的缺失的元素。
  • 注:如果某个位置已经被置为负数了,那就不要管,因为负负得正。

实现代码:

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
    int count = 0;	//用来记录[1,n]中出现的元素个数
    
    //利用出现的元素将数组的某些位置置为负数
    for(int i = 0; i < numsSize; i++)
    {
        if(nums[abs(nums[i]) - 1] > 0)
        {
            nums[abs(nums[i]) - 1] *= -1;
            count++;
        }
    }
    
    *returnSize = numsSize - count;	//得到返回数组的大小
    
    int* ret = (int*)malloc(sizeof(int) * (*returnSize));	//申请内存
    
    count = 0;	//用来算缺失元素的个数
    
    //找到缺失元素
    for(int i = 0; i < numsSize; i++)
    {
        if(nums[i] > 0)
        {
            ret[count] = i + 1;
            count++;
        }
    }
    
    return ret;	//返回结果
}

到了这里,关于每日一题——找到消失的数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode:【448. 找到所有数组中消失的数字】题解

    题目 给你一个含  n  个整数的数组  nums  ,其中  nums[i]  在区间  [1, n]  内。请你找出所有在  [1, n]  范围内但没有出现在  nums  中的数字,并以数组的形式返回结果。 难度: 简单 题目链接:448. 找到所有数组中消失的数字 示例1 示例2 解题思路: 题目意思是再在有 n

    2024年02月11日
    浏览(40)
  • 找到所有数组中消失的数(C语言详解)

    题目:找到所有数组中消失的数 题目详情: 给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1,n] 内。请你找出所以在 [1,n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。 示例1: 输入:nums = [ 4,3,2,7,8,2,3,1 ] 输出:[ 5,6 ]  示例2: 输入:nums

    2024年02月11日
    浏览(32)
  • 2023-09-05 LeetCode每日一题(从两个数字数组里生成最小数字)

    点击跳转到题目位置 给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ,每个数组中的元素 互不相同 ,请你返回 最小 的数字,两个数组都 至少 包含这个数字的某个数位。 示例 1: 示例 2: 提示: 1 = nums1.length, nums2.length = 9 1 = nums1[i], nums2[i] = 9 每个数组中,元素 互不相

    2024年02月09日
    浏览(60)
  • (数组与矩阵) 剑指 Offer 03. 数组中重复的数字 ——【Leetcode每日一题】

    难度:简单 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入 : [2, 3, 1, 0, 2, 5, 3] 输出 :2 或

    2024年02月16日
    浏览(40)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(41)
  • C语言每日一题(22)合并两个有序数组

    力扣网 88. 合并两个有序数组 给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并后数组

    2024年02月08日
    浏览(43)
  • 【C语言】每日一题(寻找数组的中心下标)

    寻找数组的中心下标,链接奉上 ​​​​​​​思路: 依旧是我们的老朋友,暴力循环。 1.可以利用外层for循环,循环变量为数组下标,在循环内分别求出下标左边与右边的sum 2.在边界时讨论, 当下标为左边界(nums[0])时,left sum=0;当下标为右边界(nums[numsSize-1)时,r

    2024年02月13日
    浏览(48)
  • 【C语言】每日一题(除自身以外数组的乘积)

    添加链接描述,链接奉上 暴力循换真的是差生法宝,简单好懂,就是不实用,大多数的题目都会超过时间限制(无奈) 思路: 1.写一个除自身的数组乘积函数 2.利用 for循环遍历数组 , i 作为循环变量,当遍历到 i 时,就求出除 i 以外的数组乘积 3.放入返回数组中 代码实现

    2024年02月10日
    浏览(39)
  • 算法每日一题: 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分

    Hello,大家好,我是星恒 呜呜呜,今天给大家带来的又是一道经典的动归难题。 题目:leetcode 410 给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k_ 个非空的连续子数组。 设计一个算法使得这 k _个子数组各自和的最大值最小。 示例: 示例 1: 示例 2: 示例

    2024年01月22日
    浏览(47)
  • C语言每日一题:6.移除元素+合并两个有序数组。

    一:暴力查找的方法: 1.找到对应val值的下标,返回数组的下标。 2.删除对应的下标,从前向后用后面覆盖前面。当后一个是数组最后一个数值是就赋值结束了(注意数组越界的问题)。 3.删除了一个数之后数组元素个数要–。 4.查找和删除是在一个循环里面因为val的值可能

    2024年02月15日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包