缺失的第一個(gè)正數(shù)

這到題再我之前面試的時(shí)候遇見(jiàn)一個(gè)非常相像的，所以就拿來(lái)記錄一下。

import org.junit.Test;

import java.util.Arrays;

/**
 * 缺失的第一個(gè)正數(shù)
 *
 * @author szw<szw0814 @ 1 6 3 . com> 2020/9/14
 *
 * 給你一個(gè)未排序的整數(shù)數(shù)組，請(qǐng)你找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。
 * 輸入: [1,2,0]
 * 輸出: 3

 * 輸入: [3,4,-1,1]
 * 輸出: 2
 */
public class findPositiveNumber {

    @Test
    public void test(){
        int[] nums = {1,2,0};
        System.out.println(firstMissingPositive(nums));
    }

    /**
     *一旦數(shù)組中出現(xiàn)小于等于0的數(shù)，或者是大于等于n+1的數(shù)，那么1-n中就必定有數(shù)字缺失（這里n代表數(shù)組的長(zhǎng)度）
     */
    public int firstMissingPositive(int[] nums) {

        // 計(jì)算數(shù)組長(zhǎng)度
        int n = nums.length;
       Arrays.sort(nums);
       // 需要想到：結(jié)果集中一定是從1開(kāi)始的，如果是小于0的數(shù)不管，從1開(kāi)始做對(duì)比，如果數(shù)組比rs大了。那么確是的數(shù)就找到了
        int rs = 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] > rs){
                break;
            }else if(nums[i] == rs){
                rs++;
            }
        }
        return rs;
    }
}