Make writing a habit together! This is the 10th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

Given an unsorted integer array nums, find the smallest positive integer that does not appear in it.

You implement a solution with O(n) time complexity and use only constant level extra space.

Thought analysis

If the O(n) time complexity is not considered, we can solve this problem by sorting. If the constant level space complexity is not considered, we can also throw elements into the monotonic stack or heap, but this solution is not feasible under the current requirements.

But there’s something in common with all of these schemes, and it makes sense if you want to sort something or nothing, it makes it easier to find the smallest positive number.

The problem itself has a condition, we assume that for elements, only 0-n exists, to find the smallest missing positive number (because there is 0, there must be a minimum positive number or n+1).

So if the element is not 0-n, it must be in 0-n, so we just sort the elements that are 0-n.

Most sorts are difficult to order in O(n) time because the result set is not finite, but under the condition of the result set is limited, we can achieve a sort of O(n) time by switching sorts.

The specific implementation

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

Copy the code

conclusion

The problem itself is not that difficult, just that it is not easy to swap ideas, but once you have done it, you can do it.