如何用C++找出第一個正整數

這篇文章主要介紹“如何用C++找出第一個正整數”，在日常操作中，相信很多人在如何用C++找出第一個正整數問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何用C++找出第一個正整數”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

1. 題目描述

給你一個未排序的整數數組，請你找出其中沒有出現的最小的正整數。
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
提示：
你的算法的時間復雜度應為O(n)，并且只能使用常數級別的額外空間。

2. 解題思路

/*
解題思路：
1、第一個正數為：大于0的整數，如1、2、3、4、5...
2、將數字放到正確的位置： nums[i]:存儲在下標為nums[i]-1位置,不符合該規則的跳過
3、遍歷數組返回第一個: nums[i]!=i+1的數，為缺失的第一個正數，否則返回numsSize+1
*/

3. 測試結果

4. 解法1

int firstMissingPositive(int* nums, int numsSize) {
    //mid臨時變量用于數據交換
    int mid = 0;
    //遍歷nums數組
    for (int i = 0; i < numsSize; i++)
    {
        //將 nums[i]:存儲在下標為nums[i]-1位置,不符合該規則的跳過
        while ((nums[i] > 0) && (nums[i] < numsSize + 1) && (nums[i] != nums[nums[i] - 1])) {
            mid = nums[i];
            nums[i] = nums[mid - 1];
            nums[mid - 1] = mid;
        }
    }
    //設置返回值變量res,如果所有值位置都正確，則返回numsSize+1
    int res = numsSize + 1;
    //遍歷數組，返回第一個位置不正確的數
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] != i + 1) {
            res = i + 1;
            break;
        }
    }
    return res;
}

到此，關于“如何用C++找出第一個正整數”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！