[LeetCode] 41. First Missing Positive

轉自LeetCode

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

<Solution>

這題比較麻煩的部分是，題目要求時間複雜度 O(n) 且空間複雜度要 O(1)

解題想法如下

• 每個 index 放相對應的數值，例如 index 0 放的是 1，index 1 放的是 2。關係是 A[i] = A[A[i] - 1]

• 如果A[i] > 0 且 A[i] <= nums.size()，就檢查 A[i] == A[A[i] - 1]，不是的話就對調

• 找第一個不符合規則到 index，回傳 index + 1

• 如果找不到，那就代表沒有缺失 positive integer，且是升冪排列，所以回傳 nums.size() + 1

code 如下

c++

	class Solution {
	public:
	int firstMissingPositive(vector<int>& nums) {
	if(nums.empty()) {
	return 1;
	}
	int i = 0;
	while(i < nums.size()) {
	if(nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i] - 1]) {
	//> means 1 should be put in A[0], 2 shoud be put in A[1]
	swap(nums[i], nums[nums[i]-1]);
	}
	else {
	++i;
	}
	}
	//> find first missing positive
	for(int i = 0; i < nums.size(); i++) {
	if(nums[i] != i+1) {
	return i+1;
	}
	}
	//> means there is no missing positive and also in increaing order
	return nums.back() + 1;
	}
	};

view raw firstMissingPositive.cpp hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun firstMissingPositive(nums: IntArray): Int {
	for(i in nums.indices) {
	while(nums[i] > 0 && nums[i] <= nums.size && nums[nums[i]-1] != nums[i]) {
	nums[i] = nums[nums[i]-1].also { nums[nums[i]-1] = nums[i] }
	}
	}
	for(i in nums.indices) {
	if(nums[i] != i+1) {
	return i+1
	}
	}
	return nums.size + 1
	}
	}

view raw first_missing_positive.kt hosted with ❤ by GitHub