找到所有數組中消失的數字,鏈接奉上。
這里簡單說一下,因為還沒有接觸到
動態內存,數據結構
,所以知識有限,也是盡力而為,結合題庫的評論區
找到了適合我的解法
,以后有機會,會補上各種解法
方法
- 暴力循環
- 排序+分情況討論
暴力循環
暴力循環依舊是最容易想到的,但是越容易想到的往往更耗費時間,也就意味著更容易超出時間界限。
思路:
雙重
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;
}
歡迎大家糾錯與討論。