lintcode 189. First Missing Positive（要小心處理！?。。。。?/h2>

image.png

https://algorithm.yuanbin.me/zh-hans/integer_array/first_missing_positive.html

核心代碼為那幾行交換，但是要很好地處理各種邊界條件則要下一番功夫了，要能正常的交換，需滿足以下幾個(gè)條件：

(1) A[i] 為正數(shù)，負(fù)數(shù)和零都無(wú)法在桶中找到生存空間...
(2) A[i] \leq size 當(dāng)前索引處的值不能比原數(shù)組容量大，大了的話也沒(méi)用啊，肯定不是缺的第一個(gè)正數(shù)。
(3) A[i] != i + 1, 已滿足條件了無(wú)需交換。
(4)A[i] != A[A[i] - 1], 避免欲交換的值和自身相同，否則有重復(fù)值時(shí)會(huì)產(chǎn)生死循環(huán)。
如果滿足以上四個(gè)條件就可以愉快地交換彼此了，使用while循環(huán)處理，此時(shí)i并不自增，直到將所有滿足條件的索引處理完。

class Solution {
public:
    /**
     * @param A: An array of integers
     * @return: An integer
     */
    int firstMissingPositive(vector<int> &A) {
        // write your code here
        for(int i = 0; i < A.size(); i++){
            if(A[i] > 0  && A[i] <= A.size() && A[i] != A[A[i] - 1]){
                int tmp = A[i];
                A[i] = A[A[i] -1];
                A[tmp -1] = tmp;
                i--;
            }
        }
        for(int i = 0; i < A.size(); i++){
            if(A[i] != i+1){
                return i+1;
            }
        }
        return A.size()+1;
    }
};

另外一個(gè)要注意的點(diǎn)?。?！就是交換的時(shí)候：

                int tmp = A[i];
                A[i] = A[A[i] -1];
                A[tmp -1] = tmp;

要注意A[i]已經(jīng)改變的，不能再作為索引了！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。