建站平台排行,广西网站建设哪家好,汕头市小程序定制公司,做网站凡科思路#xff1a;原地哈希表 长度为N的数组#xff0c;没有出现过的正整数一定是1~N1中的一个。 此时会思考能不能用一个哈希表来保存出现过的1~N1的数#xff0c;然后从 1 开始依次枚举正整数#xff0c;并判断其是否在哈希表中 但是题目要求常数级别的空间#xff0c;就不…
思路原地哈希表 长度为N的数组没有出现过的正整数一定是1~N1中的一个。 此时会思考能不能用一个哈希表来保存出现过的1~N1的数然后从 1 开始依次枚举正整数并判断其是否在哈希表中 但是题目要求常数级别的空间就不能使用N的哈希表了。 这里将原数组当做哈希表使用标记的办法来标记出现过的正整数最后遍历数组第一个没出现的下标1就是答案
怎么样进行标记呢
先遍历一遍数组将非正整数置为N1再遍历一遍数组将1~N正整数对应的下标位置置为负数最后遍历一遍数组第一个不是负数的位置i1就是没出现过的最小的正整数 class Solution {public int firstMissingPositive(int[] nums) {int len nums.length;for(int i 0;ilen;i){if(nums[i]0){nums[i] len1;}}for(int i 0;ilen;i){int num Math.abs(nums[i]);if(numlennum0){nums[num-1] -Math.abs(nums[num-1]);}}for(int i 0;ilen;i){if(nums[i]0){return i1;}}return len1;}
}
