Leetcode 41. First Missing Positive

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

You must implement an algorithm that runs in O(n) time and uses constant extra space.

First Missing Positive :

給定一個未排序的整數組，找出其中沒有出現的最小的正整數

Python

所有負數、0、大於len(nums)+1的數都不用考慮。而且要nums[i] == nums[nums[i]-1] 表示數字要在正確位置進行標記 (3 要放在索引为 2 的地方)

ex: [0,3,1,2]=>應該為[0,1,2,3] 3應該要在nums[3]

沒有放對的就是我們要找的，return i+1，其餘return n+1

class Solution(object):
    def firstMissingPositive(self, nums):
        n=len(nums)
        for i in range(n):
     #負數、0、大於len(nums)+1的數都不用考慮。而且數字要在正確位置進行標記 
           while nums[i]>0 and nums[i]<n and nums[i]!=nums[nums[i]-1]:
                nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]

        for i in range(n):
            # value： [1,2,3,4]
            # index： [0,1,2,3]
            #沒有放對的就是我們要找的
            if i+1!=nums[i]:
                return i+1
        return n+1

C++

遍歷所有數字去找解，超過O(n)時間 (不好)

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int k=1;
		sort(nums.begin(), nums.end());
		for(int i=0; i<nums.size(); i++){
			if(k==nums[i]){
				k++;
			}
		}
		return k;
	}
};

把1放在數組第一個位置nums[0]，2放在第二個位置nums[1]，就是把nums[i] 放在nums[nums[i] – 1]上，如果nums[i] != i + 1, 而nums[i] 為整數且不大於n，將兩者位置調換。

發現值和位置+1不匹配，就返回這個位置+1；如果都匹配，則返回數組長度+1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};