首页 > 代码库 > 【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.
题解：开始想的是用一个hashmap保存数组中的每个值，然后遍历数组看看每个值-1和+1的值在不在map里面，后来发现只要用常数空间。就只能另想方法。
其实我们可以用原来的数组作为hash表，使得A[i] = i+1，通过不停的交换做到这一点，那么最后A[i] != i+1的i+1就是missing的数；
因为数组中除了missing的值，其他值都是连续的，所以数组中可能存放的最大值是n+1；
以题目中的例子为例：
最终A[1] != 1+1 = 2，所以缺失的2；
代码如下：
1 public class Solution { 2 private void swap(int[] A,int a,int b){ 3 int temp = A[a]; 4 A[a] = A[b]; 5 A[b] = temp; 6 } 7 public int firstMissingPositive(int[] A) { 8 //make A[i] = i+1 9 for(int i = 0;i < A.length;i++){10 while(A[i] <= A.length && A[i] > 0 && A[i] != i+1 && A[i] != A[A[i]-1])11 swap(A, i, A[i]-1);12 }13 14 //find the missing one15 for(int i = 0;i < A.length;i++)16 if(A[i] != i+1 )17 return i+1;18 19 return A.length+1;20 }21 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。