找到消失的数字
题目链接
思路
一个长度为n
的数组中所有数据的范围在[1,n]
内,题目要求我们找出在[1,n]
范围内,但数组中没有出现的数字
如果可以使用额外空间,那这题就好办了。我们直接创建一个相同大小的数组,数组的每个位置代表[1,n]
的每个元素,然后遍历数组计数就行。文章来源:https://www.toymoban.com/news/detail-615557.html
我们这里主要讲不利用额外空间,直接在原数组原地修改的方法法。文章来源地址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模板网!