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

41. First Missing Positive

2024-10-13 16:53:01   206人阅读

一、题目

　　1、描述

　　　　技术分享

　　2、题意

　　　　　　返回无序数组中缺失的第一个正整数。

 

二、解答

　　1、思路：

　　　　①  数组进行排序，下标从数值为正整数开始；

　　　　② 若后面数值与前面数值重复，下标+1；

　　　　③ 返回 第一个缺失的数值，跳出循环

// 41. First Missing Positive
    public static int firstMissingPositive(int[] nums) {
    
        int len = nums.length;
        if(len == 0)    return 1;
        Arrays.sort(nums);
        int index = 0;
        
        while(index < len && nums[index] <= 0) index++;
        
        for(int i = 1; i <= len + 1; i++) {

            if(index < len) {
                if(nums[index++] != i)
                    return i;
                else  {
                    while(index < len && nums[index-1] == nums[index])
                        index++;
                }
            }
            else {
                return i;
            }
            
        }
        
        return 0;
    }

 

 

　　方法二：

　　　　The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.

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

 

三、总结

　　　　方法二还需探究。    A[A[i]-1] != A[i] 仅仅是避免死循环？

41. First Missing Positive


联系
我们