[LeetCode]41. First Missing Positive

https://leetcode.com/problems/first-missing-positive/?tab=Description

找出数组中缺失的第一个正数

当nums[i] = i + 1时视为该值放在了正确位置，while内每次swap，至少增加一个正确位置，同时在正确位置时nums[i] == nums[nums[i] - 1]。因此while循环最多执行N次，整个函数时间复杂度O(N)

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