The first positive number missing in question 41 of C language. Two methods, preprocessing, fast sorting and in situ hashing

Here's an unsorted array of integers nums , Please find the smallest positive integer that doesn't appear in it .
Please implement a time complexity of O(n) And solutions that use only constant level extra space .

Example 1：

Input ：nums = [1, 2, 0]
Output ：3

Example 2：

Input ：nums = [3, 4, -1, 1]
Output ：2

Example 3：

Input ：nums = [7, 8, 9, 11, 12]
Output ：1

Tips ：

1 <= nums.length <= 5 * 105
- 231 <= nums[i] <= 231 - 1

source ： Power button （LeetCode）
link ：https ://leetcode.cn/problems/first-missing-positive
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1 Pretreatment accelerates the discharge

Set the array size to N, The smallest known positive integer is 1, Then let the minimum positive integer missing be n=1, Then we just need to start from 1 Start , Judge n Whether in the array , If in the array , be n Add one , If it's not in the array , Then the minimum positive integer missing is still n.

But larger numbers may appear before smaller numbers , Traversal from front to back may miss some values , So you need to traverse from the beginning every time , The time complexity is O(N^2), It's too high , So we need to improve .

Let's have a quick row from small to large , The time complexity is O(Nlog⁡N), Then traverse the array from front to back according to the previous idea , The time complexity is O(N), Then the total time complexity is O(Nlog⁡N)+O(N)=O(Nlog⁡N)

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int firstMissingPositive(int* nums, int numsSize) {
    for(int i = 0; i < numsSize; i++) {
        if(nums[i] < 0) {
            nums[i] = 0;
        }
    }
    qsort(nums, numsSize, sizeof(int), cmp);
    int n = 1;
    for(int i = 0; i < numsSize; i++) {
        if(nums[i] == n) {
            n++;
        }
    }
    return n;
}

Method 2 ： In situ hash

Because the title requires us to 「 Only constant level spaces can be used 」, And the number you're looking for must be [1, N + 1] Left and right closed （ here N Is the length of the array ） In this interval . therefore , We can use the original array as a hash table . in fact , The hash table itself is actually an array ;
The number we're looking for is [1, N + 1] in , Last N + 1 We don't have to look for this element . Because in front of N When none of the elements can be found , We came back to N + 1;
that , We can take this idea ： Just put 1 This number is subscripted as 0 The location of , 2 This number is subscripted as 1 The location of , Sort out the array according to this idea . Then we iterate over the array again , The first 1 The value of an encounter is not equal to the number of subscripts , It's the first positive number we're looking for .
This idea is equivalent to writing our own hash function , The rules of this hash function are particularly simple , That is, the value is i The number of is mapped to the subscript i - 1 The location of .

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int firstMissingPositive(int* nums, int numsSize) 
{
	int ans = 0;
	int i = 0, j = 0;

	for (int i = 0; i < numsSize; ++i) 
	{
		if (nums[i] <= 0) {
			nums[i] = numsSize + 1;
		}
	}

	for (i = 0; i < numsSize; i++)
	{
		while (nums[i] >= 1 && nums[i] <= numsSize && nums[i] != nums[nums[i] - 1])
		{
			j = nums[i];
			nums[i] = nums[j - 1];
			nums[j - 1] = j;
		}
	}
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] != i + 1)
		{
			ans = i + 1;
			return ans;
		}
	}
	//for (i = 0; i < numsSize; i++)
	//	printf("%d\n", nums[i]);
	return numsSize+1;
}

int main()
{
	int nums[] = { 3, 4, -1, 1 };
	int numsSize = sizeof(nums) / sizeof(int);
	int ans = firstMissingPositive(nums, numsSize);
	printf("%d", ans);
	return 0;
}