LeetCode-41-缺失的第一个正数

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 0 <= nums.length <= 300
• -231 <= nums[i] <= 231 - 1

\41. First Missing Positive

Hard

5690990Add to ListShare

Given an unsorted integer array nums, find the smallest missing positive integer.

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

• 1 <= nums.length <= 300
• -231 <= nums[i] <= 231 - 1

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space?

解题思路

原地算法，时间复杂度O(n),空间复杂度O(1)。

构建双指针。

• R指针定义

R指针定义

• L指针定义

L指针定义

• Arr[L] > R的情况

Arr[L] > R的情况

• Arr[L] <= L的情况

Arr[L] <= L的情况

• Arr[L] = L+1的情况,有效数字

Arr[L] = L+1的情况 有效数字

• Arr[L] >L && Arr[L] <R的情况,有效数字

有效数字

• Arr[L] > R的情况 R--,有效区域缩小

R--有效区域缩小

• Arr[L] >L && Arr[L] <R的情况,Arr[L] ==ARR[Arr[L] -1],无效数字，缩减有效区域

无效数字，缩减有效区域

• L和R相遇 程序结束

L和R相遇 程序结束

class Solution {
   public static int firstMissingPositive(int[] arr) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            if (arr[l] == l + 1) {//Arr[L] = L+1的情况,有效数字 L+1
                l++;
            } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {//无效数字情况，缩减有效区域 R--
                swap(arr,l,--r);
            } else {
                swap(arr, l, arr[l] - 1);//Arr[L] >L && Arr[L] <R的情况,有效数字,填入对应的位置，L R不动
            }
        }
        return l + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

image-20210507103034121