购买网站做网页游戏,免费发布企业信息平台,北仑宁波有没有做网站,英文网站开发公司哪家好本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第五道#xff1a;缺失的第一个正数#xff08;困难#xff09; 第五道#xff1a;缺失的第一个正数#xff08;困难#xff09; 方法一#xff1a;将数组视为哈希表
class Solution {public int firstMissingPosi… 本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第五道缺失的第一个正数困难 第五道缺失的第一个正数困难 方法一将数组视为哈希表
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for (int i 0; i n; i) {if (nums[i] 0) {nums[i] n 1;}}for (int i 0; i n; i) {int num Math.abs(nums[i]);if (num n) {nums[num - 1] -Math.abs(nums[num - 1]);}}for (int i 0; i n; i) {if (nums[i] 0) {return i 1;}}return n 1;}
} 1.将负数0替换为n1变成无效数字因为我们只关心[1n]的正数。 2.标记已存在的正整数,对于每一个元素 nums[i]我们用它的绝对值 num 来表示。如果num是一个有效的数字也就是numn。那么将数组中索引num-1的元素下标记为负数。这一步结束后数组中所有出现过的正整数对应的索引位置都会被标记为负数。 3.查找第一个未被标记的位置。查找第一个仍然为正数的元素。此时返回i1。 4.如果没有找到返回n1 复杂度分析 时间复杂度O(N)其中 N 是数组的长度。 空间复杂度O(1)。 方法二置换恢复
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for (int i 0; i n; i) {while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) {int temp nums[nums[i] - 1];nums[nums[i] - 1] nums[i];nums[i] temp;}}for (int i 0; i n; i) {if (nums[i] ! i 1) {return i 1;}}return n 1;}
}除了打标记以外我们还可以使用置换的方法将给定的数组「恢复」成下面的形式 遍历数组对于每个元素将其放置在正确的位置上即把数字 nums[i] 放在索引 nums[i] - 1 的位置上。通过不断交换确保每个正整数 k 出现在索引 k-1 的位置上。检查数组再遍历一次数组找到第一个位置 i 使得 nums[i] ! i 1即第一个缺失的正整数是 i 1。返回结果如果所有位置都满足 nums[i] i 1则返回 n 1即数组长度加一的值。 复杂度分析 时间复杂度O(N)其中 N 是数组的长度。 空间复杂度O(1)。
