首页 > 代码库 > 【LeetCode】First Missing Positive 解题报告
【LeetCode】First Missing Positive 解题报告
【题目】
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0]
return 3
,
and [3,4,-1,1]
return 2
.
Your algorithm should run in O(n) time and uses constant space.
【解析】题意:给定一个数组,找出第一个缺失的正数,要求时间复杂度为O(n),空间复杂度为O(1)。
这道题为LeetCode上的一道Hard类型的题,第一次看没想出来怎么做,放了两天,然后某个空当突然就想到了解题思路:
public class Solution { public int firstMissingPositive(int[] A) { if (A == null || A.length < 1) return 1; //求数组中正数的个数cnt int cnt = 0; for (int i = 0; i < A.length; i++) { if (A[i] > 0) { cnt++; } } //用一个数组标记从0到cnt的正数是否出现过 boolean[] flag = new boolean[cnt + 1]; Arrays.fill(flag, false); for (int i = 0; i < A.length; i++) { if (A[i] > 0 && A[i] <= cnt) { flag[A[i]] = true; } } //从0到cnt第一个没有出现的正数就是要返回的结果 for (int i = 1; i <= cnt; i++) { if (!flag[i]) return i; } return cnt + 1; } }
===白高兴一场,上面解法好像不是O(1)===
正确解法如下,把正数n放在第n-1个位置上,这样从第一个位置开始,如果位置上的数不等于位置号,那么就是第一个缺失的正数:
public class Solution { public int firstMissingPositive(int[] A) { if (A == null || A.length < 1) return 1; //把小于等于A.length的正数A[i]放到第A[i]-1个位置上 for (int i = 0; i < A.length; i++) { while (A[i] > 0 && A[i] <= A.length && A[A[i] - 1] != A[i]) { int tmp = A[A[i] - 1]; A[A[i] - 1] = A[i]; A[i] = tmp; } } for (int i = 0; i < A.length; i++) { if (A[i] != i + 1) { return i + 1; } } return A.length + 1; } }
【LeetCode】First Missing Positive 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。