题目描述:
给定一个无序整型数组arr,找到数组中未出现的最小整数
例子
arr=[-1,2,3,4] return 1
arr=[1,2,3,4] return 5
时间复杂度O(n) 空间复杂度O(1)
解题思路: (1) arr为整数1,2,3…N的一个随机排列,那个未出现的最小正整数就是N+1。(2) arr中有小于1或者大于N的数出现(我们称之为“不合法”的数),则未出现的最小正整数一定在1到N中间(因为数组一共只有N个数,如果出现不合法的数,则出现的1到N之间的数的个数一定小于N,故一定有没有出现的数)。
实现函数
int missNum(vector<int> nums){ int l = 0; // 1-l 已经有 int r = nums.size(); // l+1-r想要有 while (l < r) { if (nums[l] == l + 1) { l++; } // nums[l] 减去 1 表示数nums[l] 应该在的位置 else if (nums[l] < l + 1 || nums[l] > r || nums[nums[l] - 1] == nums[l]) { r--; nums[l] = nums[r]; } else{ swap(nums[l], nums[nums[l] - 1]); } } return l + 1;} 12345678910111213141516171819202122