Given an unsorted integer array, find the smallest missing positive integer.
- Example 1:
- Input: [1,2,0]
- Output: 3
- Example 2:
- Input: [3,4,-1,1]
- Output: 2
- Example 3:
- Input: [7,8,9,11,12]
- Output: 1
- Note:
- Your algorithm should run in O(n) time and uses constant extra space.
桶排序思想: 把东西放在它应处的位置.
本题如果是三个数字, 那这三个位置是开给 123 的, 如果 5 个数字, 五个位置是开给 12345 的. 如果进来无效数字:<=0 或者 > length, 那就会占掉本来期待的数字的位置.
1. 遍历数字, 让所有有效数字都跑到自己该在的桶里.
2. 遍历每个桶, 第一个发现的装错数字的桶, 它本应装的数字就是我们期待的 first missing positive.
细节:
1. 让所有有效数字跑到自己桶里的方法就是, 如果看到一个数, 它在当前长度的数组里应该有一席之位([1, length]), 而且那个位置上当前不是已经有这个数了(nums[nums[i] - 1] != nums[i]), 那就 swap. 同时注意的是换过来的数字还没检查过, 要接着检查, 所以这里用 while 循环不是用 if.
2. 注意最后没有发现装错东西的桶, 就说明现在都按 12345 排了什么数字都不缺, 那还要返回下一个 length+1 作为答案.
3. 本题 0 或者负数或者多出来的无家可归的 [1,length] 数字都是无效数字, 不用处理, 就做一些占位符, 不要挡道那些应该可以放到正确位置的数字的道就行, 等着最后一轮清扫被揪出来.
实现
- class Solution {
- public int firstMissingPositive(int[] nums) {
- if (nums == null) {
- return 1;
- }
- for (int i = 0; i <nums.length; i++) {
- // numbers that can be set in right place, and the place is not occupied by another this number.
- while (nums[i]>= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
- swap(nums, i, nums[i] - 1);
- }
- }
- for (int i = 0; i < nums.length; i++) {
- if (nums[i] != i + 1) {
- return i + 1;
- }
- }
- return nums.length + 1;
- }
- private void swap(int[] nums, int i, int j) {
- int temp = nums[i];
- nums[i] = nums[j];
- nums[j] = temp;
- }
- }
来源: http://www.bubuko.com/infodetail-2769650.html