2015年9月21日星期一

Leetcode 41 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.

Solution 1: if the nums are 1,2,...n. We put it in final position. Then iterate the array again. 1st number not in position is the missing one.
 public 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[i]!=nums[nums[i]-1])   
         swap(nums,i,nums[i]-1);  
     for (int i=0; i<n; i++)   
       if (nums[i]!=i+1) return i+1;  
     return n+1;  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

没有评论:

发表评论