---
# System prepended metadata

title: Leetcode 41. First Missing Positive

---

# Leetcode 41. First Missing Positive

## 題目敘述:
給定一個一維陣列，尋找最小缺失正整數

示範測資:
![](https://i.imgur.com/C6RwD9o.png)

## 解題思路:
將題目給定陣列sort過此題將會變得非常輕易，我是將陣列用qsort的方式從大到小排序，先檢查nums[0]/最大值/是否<=0如果是回傳1，若反之從後掃回去，先假定最小缺失正整數(min)為1，如果跟min相同則min++，若為連續數字則為min-1可以continue掉，其他情況則回傳min，若此陣列為連續整數則須在迴圈外回傳min。

## 注意事項:
1.sort之方法僅能用O(nlogn)的排序法，其他排序法將會超時ex:泡沫排序法O(n^2)。

## C的參考程式碼
```
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)b - *(int*)a );
}
int firstMissingPositive(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmpfunc);
    if(nums[0]<=0)return 1;
    int min = 1;
    for(int i = numsSize-1;i>=0;i--){
        if(nums[i]<=0)continue;
        if(nums[i]==min)min++;
        if(nums[i]==min-1)continue;
        else{
            return min;
        }
    }
    return min;
}
```
