用一个标记数组来记录1到n-1之间的数是否出现过,遍历完做完标记之后再遍历一遍数组,找出第一个标记值未改变的即是没有出现过的,
一般情况就是原数组中出现了小于n的数和大于n的数,那么就把小于n的数在标记数组中改变标记值,大于等于n的数不管
特殊情况:对于数组中的数刚好是1到n-1每个数都出现过一遍,那么没出现的第一个数就是n.
对于数组中的数均大于等于n时,标记数组完全没变化,没出现过的第一个数仍旧是n.
int minNumberDisappeared(int* nums, int numsLen ) { int* arr = (int*)malloc(sizeof(int) * numsLen); int i = 0; for(i = 0; i<numsLen; i++) arr[i] = 0; //初始全标记为0 for(i = 0; i<numsLen; i++){ if(nums[i] > 0 && nums[i] <= numsLen) arr[nums[i]-1] = 1; //改变标记值 } for(i = 0; i<numsLen; i++){ if(arr[i] == 0) //寻找未出现的 break; } return i+1; }