解题思路:
原地哈希
就相当于,让每个数字n都回到下标为n-1的家里。
而那些没有回到家里的就成了孤魂野鬼流浪在外,他们要么是根本就没有自己的家(数字小于等于0或者大于nums.size()),要么是自己的家被别人占领了(出现了重复)。
class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;for (int i = 0; i < len; i++) {// 不能使用nums[i]-1!=i来判断,外面同时套了一层nums[]while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i])swap(nums, i, nums[i] - 1);}for (int i = 0; i < len; i++) {if (nums[i] != i + 1)return i + 1;}return len + 1;}public void swap(int[] nums, int idx1, int idx2) {int tmp = nums[idx1];nums[idx1] = nums[idx2];nums[idx2] = tmp;}
}