這四道題都是與數(shù)組中的數(shù)字相關(guān)的，包括找到順序表中缺失的數(shù)字、找到順序表中缺失的最小的正數(shù)、尋找無重復(fù)的順序表中缺失的數(shù)字、尋找順序表中重復(fù)的數(shù)字。
這類問題皆可用 nums[i] 與 nums[nums[i]-1] 以及 i+1 的關(guān)系來解決。

268. Missing Number

給定包含n個(gè)不重復(fù)數(shù)字的數(shù)組，其值在0~n（共n+1個(gè)數(shù)）之間，求出數(shù)組中漏掉的那個(gè)數(shù)。

本題意思就是，一共有n+1個(gè)不重復(fù)的連續(xù)的數(shù)，需要放在數(shù)量為n的數(shù)組中，則必然有1個(gè)數(shù)放不進(jìn)去，現(xiàn)在需要求出這個(gè)數(shù)。可利用數(shù)組排序來解。排序后的數(shù)組，每個(gè)位置 i 上對(duì)應(yīng)的數(shù)字nums[i] 應(yīng)該有 nums[i] = i ，否則就表示該數(shù)字缺失，此處存的是后一個(gè)數(shù)字。

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int i;
        for(i = 0; i<nums.length; i ++)
            if(i != nums[i])
                return i;
        return i;
    }
}

41. First Missing Positive

給定一個(gè)無序數(shù)組，尋找該數(shù)組中缺失的最小的正數(shù)。要求運(yùn)行時(shí)間O(n)

本題的意思就是尋找一個(gè)正整數(shù)，它不在給定的數(shù)組中，且小于數(shù)組中所有的正整數(shù)。
解題思路：將數(shù)組排序，找到最小的不在自己位置上的數(shù)字即可。
（1）. 我們不需要關(guān)心數(shù)組中的重復(fù)數(shù)字和非正整數(shù)（0及負(fù)數(shù)）;
（2）. 若給定數(shù)組中有很大的數(shù)，比如24，而數(shù)組長度n僅為4，則在計(jì)算時(shí)不需考慮過大的數(shù)字，所求的整數(shù)必然在 1~n 的區(qū)間內(nèi)；
（3）. 關(guān)鍵點(diǎn)： nums[i] 與 nums[nums[i]-1] 的關(guān)系。正常而言，在只考慮正整數(shù)的情況下，排序后的數(shù)組，第 i 位的數(shù) nums[i] 應(yīng)該等于 i +１，因此，若對(duì)應(yīng)位置上的數(shù)值不符合該規(guī)則，則表示此數(shù)缺失。
（4）. 就地排序：遍歷一遍數(shù)組，把不在自己位置上的 nums[i] 就地交換到它應(yīng)該在的地方去，即第 nums[i] - 1位數(shù)，即 nums[nums[i]-1] = nums[i] .

public int firstMissingPositive(int[] nums) {
        int temp;
        int i = 0;
        while( i < nums.length) {
            if(nums[i] < nums.length && nums[i] > 0  && nums[i] != nums[nums[i] - 1]) {
                temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }
            else 
                i++;    
        }
        for(i = 0; i< nums.length; i++) {
            if (nums[i] != (i+1))
                return i+1; 
        }
        return i+1;
        
    }

448. Find All Numbers Disappeared in an Array

給定一個(gè)長為n的數(shù)組，其中的元素值范圍在1~n之間，每個(gè)數(shù)最多重復(fù)兩次，求出該范圍內(nèi)沒出現(xiàn)在數(shù)組中的所有整數(shù)。

本題限定了數(shù)組中的元素范圍，即n個(gè)元素，放入長為n的數(shù)組中，但此題中的元素可以重復(fù)，因此會(huì)有整數(shù)未出現(xiàn)。
解題思路：此題依然可以利用 nums[i] 與 nums[nums[i]-1] 的關(guān)系，因?yàn)橹挥衝個(gè)數(shù)，因此其排序后元素值和位置是有聯(lián)系的，若某一位上沒有這種關(guān)聯(lián)，則其必然有問題。
（1） 對(duì)于重復(fù)的數(shù)字，我們不處理它，可將其任意交換，最后必然會(huì)交換到缺失的整數(shù)所在的位置；
（2） 由于存在將數(shù)字 nums[i] 交換到其對(duì)應(yīng)位置時(shí)，該位置已被其重復(fù)數(shù)字 nums[i]' 占據(jù)，導(dǎo)致死循環(huán)的情況，所以在比較時(shí)要注意目標(biāo)位置上的值是否已經(jīng)正確；
（3） 注意： 第 i 位被比較并且交換了數(shù)值后，此時(shí)的 nums[i] 以及是一個(gè)新的值了，需要重新判斷其對(duì)應(yīng)關(guān)系，因此要保證在下一次循環(huán)時(shí) i 的值仍不變。

    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> l = new ArrayList<Integer>();
        int i, j;
        for (i = 0; i<nums.length;i++) {
            if(nums[i] != i+1 && nums[nums[i]-1] != nums[i]) {
                //swap(nums[i], nums[nums[i] - 1], 1);
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
                i --;//下一輪繼續(xù)比較新的 nums[i]
            }
        }
        for (i = 0; i<nums.length;i++) {
            if(nums[i]!= i+1)
                l.add(i + 1);
        }
        return l;
    }