Algorithm

[LeetCode 41] First Missing Positive [C] [Runtime : 3 MS]

顿搜

2017-06-20

0 评论

576 阅读

正在检测是否收录...

06/20

1. Runtime Distribution

2. Submission Details

3. Description

Given an unsorted integer array, find the first missing positive integer.
Your algorithm should run in O(n) time and uses constant space.

4. Example

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

5. Explanation

The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.

6. Code

int firstMissingPositive(int * nums, int numsSize)
{
    for(int i = 0; i< numsSize; i++)
    {
        if(nums[i] > 0 && nums[i] <= numsSize && nums[i] != i + 1)
        {
            if(nums[i] != nums[nums[i] - 1])
            {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i--] = tmp;
            }
        }
    }

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

7.Test

#include<stdio.h>

int firstMissingPositive(int * nums, int numsSize)
{
    for(int i = 0; i< numsSize; i++)
    {
        if(nums[i] > 0 && nums[i] <= numsSize && nums[i] != i + 1)
        {
            if(nums[i] != nums[nums[i] - 1])
            {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i--] = tmp;
            }
        }
    }

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

int main()
{
    int nums[] = { 3, 4, -1, 1 };
    printf("%d\n", firstMissingPositive(nums, 4));
    system("pause");
    return 0;
}

Array

朗读