首页 > 代码库 > 41. First Missing Positive

41. First Missing Positive

2024-08-24 21:17:03   218人阅读

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.

example [-1,-2, 1,3];

i ++;  

i++ ;

i = 2  nums[2] = 1;  nums[nums[2] -1] = nums[0] exchange with nums[2] -> [1, -2, -1, 3]

i++;

i=3 nums[3] = 3 -> nums[2] exchange with nums[3] - > [1,-2,3,-1];

out of loop

anther loop  nums[0]= 1 got, nums[1] =-2 return i+1 -> 2

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0 ;
        while(i < nums.length){
            if(nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length) i++;
            else if(nums[i] != nums[nums[i]-1]) swap(nums, i, nums[i]-1);
            else i++;
        }
         i = 0;
        while(i < nums.length && i+1 == nums[i]) i++;
        return i+1;
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

 

41. First Missing Positive


联系
我们