给定一个无重复元素的整数数组nums,请你找出其中没有出现的最小的正整数
进阶: 空间复杂度 ,时间复杂度
数据范围:
int minNumberDisappeared(int* nums, int numsLen ) { int HashTable[500000] = {0}, i; for (i = 0; i < numsLen; i++) { if(nums[i]<=sizeof(HashTable)) HashTable[nums[i]-1] = 1; } for (i = 0; i < sizeof(HashTable); i++) { if(HashTable[i] == 0) return i+1; } return sizeof(HashTable)+1; }
int minNumberDisappeared(int* nums, int numsLen ) { // write code here //缺失的第一个正整数只可能在1~500001中取 int a[500001]; int i; //遍历nums并在a中记录 for (i = 0; i < numsLen; i++){ if (nums[i] > 0 && nums[i] <=500000) a[nums[i]]++; } //找到第一个出现次数为0的下标 for (i = 1; i < 500001; i++){ if (a[i] == 0) return i; } //前500000个数字没有,那么只可能是500001了 return 500001; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param numsLen int nums数组长度 * @return int整型 */ int minNumberDisappeared(int* nums, int numsLen ) { // write code here int i,max=-111111; int c[500001]={0}; for(i=0;i<numsLen;i++) { if(nums[i]>=1) c[nums[i]]++; if(nums[i]>max) max=nums[i]; } for(i=1;i<=max;i++) { if(c[i]==0) return i; } return max+1; }