找到所有数组中消失的数字,链接奉上。
这里简单说一下,因为还没有接触到
动态内存,数据结构
,所以知识有限,也是尽力而为,结合题库的评论区
找到了适合我的解法
,以后有机会,会补上各种解法
方法
- 暴力循环
- 排序+分情况讨论
暴力循环
暴力循环依旧是最容易想到的,但是越容易想到的往往更耗费时间,也就意味着更容易超出时间界限。
思路:
双重
for
循环,外部控制1~n
个数,内部遍历nums
数组,两两比较
,记录
没有出现的数字,即为消失的数字
代码实现:
static int arr[99999];//创建数组
int* finddisappearednumbers(int* nums, int numssize, int* returnsize)
{
int count = 0;//计数器
int n = 0;
for (int j = 1; j <= numssize; j++)
{
count = 0;//每次进入要重置
for (int i = 0; i < numssize; i++)
{
if (j == nums[i])
{
count++;
break;
}
}
if (count == 0)//为0说明未出现
arr[n++] = j;
}
*returnsize = n;
return arr;
}
排序+分情况讨论
思路:
排序是为了让数组有序,更好的进行操作
那么分情况讨论是怎么一回事
将1~n
设为循环变量i
,进行遍历,
left=0
设为下标,从0
开始根据情况left++
再将nums[left]与i比较
当i==nums[left]
时left++
,因为会有重复的数字,比如1 2 2 2
,这时,可以使用while循环
当i!=nums[left]
时,将i
放入结果数组
注意:
数组有时会出现n(也就是numssize
)大于当前数组最大值(nums[numssize-1]
)的情况,也就是类似:1 2 2 2
的情况,所以while中的left会超出界限,这时left==numssize
,我们将剩下的for循环中未开始的i
依次赋值给结果数组
代码实现:
int cmp(int* a, int* b)
{
return *a - *b;
}
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
qsort(nums,numsSize,sizeof(int),cmp);
int* res=malloc(sizeof(int) * numsSize);//结果数组,result
*returnSize=0;
int left=0;
for(int i=1;i<=numsSize;i++)
{
if(left<numsSize&&i!=nums[left])//注意:left要放前边,防止短路发生
{
res[(*returnSize)++]=i;
//*returnsize随着结果数组的增加而增加,
//最后返回的就是数组大小
}
if(left==numsSize)
{
res[(*returnSize)++]=i;
}
//while要在最后进行,因为在前边会改变left
//影响两个if的判断
while(left<numsSize&&i==nums[left])
{
left++;
}
}
return res;
}
欢迎大家纠错与讨论。