Question: Given an unsorted list of integers, find out the first missing positive.
Problem Description: http://oj.leetcode.com/problems/first-missing-positive/
Examples: [1, 2, 0] should return 3; [3, 4, -1, 1] should return 2. Can you do it with O(n) time complexity and O(1) constant space?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: int firstMissingPositive(int A[], int n) { bool *arr = new bool[n + 1]; // O(n) space for (int i = 0; i < n; i ++) { if ((A[i] >= 0) && (A[i] <= n)) { arr[A[i]] = true; // mark A[i] present } } // up to this bit, we've actually sorted the numbers for (int i = 1; i <= n; i ++) { if (!arr[i]) return i; // not marked, so missing } return n + 1;// all marked, so the first missing is n + 1 } }; |
class Solution { public: int firstMissingPositive(int A[], int n) { bool *arr = new bool[n + 1]; // O(n) space for (int i = 0; i < n; i ++) { if ((A[i] >= 0) && (A[i] <= n)) { arr[A[i]] = true; // mark A[i] present } } // up to this bit, we've actually sorted the numbers for (int i = 1; i <= n; i ++) { if (!arr[i]) return i; // not marked, so missing } return n + 1;// all marked, so the first missing is n + 1 } };
There are some hints to solve this problem nicely. n integers are given (negatives, zero and positives). So if the worst case, all numbers are positives (1, 2, 3, … n), the first missing positive would be n + 1. In all other cases, the first missing positive would be from 1 to n inclusive.
It is unsorted array. We create another array (O(n)), to hold the booleans that if numbers appear in inputs. Initialize the array to all false (which can be omitted by default), iterative over the inputs, and mark (if the value in range) the corresponding boolean to true meaning that this number is not missing. At the end we would just have to check from index one to the end that if the corresponding boolean is false. If it is false, it means this number has not appeared in the inputs, so it is the first missing positive!
The first half of the algorithm acts as like a index sorting algorithm where you place element to the position according to its index.
The overall algorithm complexity if O(n).
Using Set
We can use STL:set to mark the appearance for the positive numbers:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: int firstMissingPositive(vector<int>& nums) { unordered_set<int> cache; for (int i = 0; i < nums.size(); i ++) { if (nums[i] > 0) { cache.insert(nums[i]); } } for (int i = 1; ; i ++) { if (!cache.count(i)) { // first missing positive return i; } } } }; |
class Solution { public: int firstMissingPositive(vector<int>& nums) { unordered_set<int> cache; for (int i = 0; i < nums.size(); i ++) { if (nums[i] > 0) { cache.insert(nums[i]); } } for (int i = 1; ; i ++) { if (!cache.count(i)) { // first missing positive return i; } } } };
O(n) time and constant space
We can re-arrange the elements so that the integer x should be in the array nums[x – 1]. We repeatedly swap the elements until they are in correct places or out of the range (non-positive or larger than the size of array). The answer would be the first element that is not in its position.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ++ i) { int x = nums[i]; while (x > 0 && x <= n && nums[x - 1] != x) { // element is not in its position swap(nums[i], nums[x - 1]); x = nums[i]; } } for (int i = 0; i < n; ++ i) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; } }; |
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ++ i) { int x = nums[i]; while (x > 0 && x <= n && nums[x - 1] != x) { // element is not in its position swap(nums[i], nums[x - 1]); x = nums[i]; } } for (int i = 0; i < n; ++ i) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; } };
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Coding Exercise - Length of Last Word - C++ - Online Judge
Next Post: Coding Exercise - Climbing Stairs - Fibonacci Numbers - C++ - Online Judge