重庆十大房地产公司_龙岩seo培训_今日国家新闻_今天上海重大新闻事件

思路

关键有两点

原地哈希

把1-len的数分别映射到下标为0 - len-1的地方中

交换后，接着查看下标i被交换过来的数，直到他到了该到的位置或者超出范围

使用while，把不满足映射关系的点一直交换，直到下标指向的位置符合要求

代码

class Solution {public int firstMissingPositive(int[] nums) {// 哈希的思想，进行原地哈希// 下标为i，应该存放i+1int len = nums.length;for(int i = 0; i < len; i++){// 把i下标的数放在该放的位置，交换后，i下标来新数了，接着交换while(nums[i] > 0 && nums[i] <= len  && nums[nums[i] - 1] != nums[i] ){int tmp = nums[ nums[i]-1 ];nums[ nums[i]-1 ] = nums[i];nums[i] = tmp;}}for(int i = 0; i < len; i++){if(nums[i] != i + 1){return i + 1;}}return len + 1;}
}