LeetCode 数字与位置关系的题（268、287、448、41）

这四道题都是与数组中的数字相关的，包括找到顺序表中缺失的数字、找到顺序表中缺失的最小的正数、寻找无重复的顺序表中缺失的数字、寻找顺序表中重复的数字。
这类问题皆可用 nums[i] 与 nums[nums[i]-1] 以及 i+1 的关系来解决。

268. Missing Number

给定包含n个不重复数字的数组，其值在0~n（共n+1个数）之间，求出数组中漏掉的那个数。

本题意思就是，一共有n+1个不重复的连续的数，需要放在数量为n的数组中，则必然有1个数放不进去，现在需要求出这个数。可利用数组排序来解。排序后的数组，每个位置 i 上对应的数字nums[i] 应该有 nums[i] = i ，否则就表示该数字缺失，此处存的是后一个数字。

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

给定一个无序数组，寻找该数组中缺失的最小的正数。要求运行时间O(n)

本题的意思就是寻找一个正整数，它不在给定的数组中，且小于数组中所有的正整数。
解题思路：将数组排序，找到最小的不在自己位置上的数字即可。
（1）. 我们不需要关心数组中的重复数字和非正整数（0及负数）;
（2）. 若给定数组中有很大的数，比如24，而数组长度n仅为4，则在计算时不需考虑过大的数字，所求的整数必然在 1~n 的区间内；
（3）. 关键点： nums[i] 与 nums[nums[i]-1] 的关系。正常而言，在只考虑正整数的情况下，排序后的数组，第 i 位的数 nums[i] 应该等于 i +１，因此，若对应位置上的数值不符合该规则，则表示此数缺失。
（4）. 就地排序：遍历一遍数组，把不在自己位置上的 nums[i] 就地交换到它应该在的地方去，即第 nums[i] - 1位数，即 nums[nums[i]-1] = nums[i] .

符号	数组元素值	所在位置
nums[0]	1	0
nums[1]	2	1
...	...	...
nums[i]	i+1	nums[i] - 1

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

给定一个长为n的数组，其中的元素值范围在1~n之间，每个数最多重复两次，求出该范围内没出现在数组中的所有整数。

本题限定了数组中的元素范围，即n个元素，放入长为n的数组中，但此题中的元素可以重复，因此会有整数未出现。
解题思路：此题依然可以利用 nums[i] 与 nums[nums[i]-1] 的关系，因为只有n个数，因此其排序后元素值和位置是有联系的，若某一位上没有这种关联，则其必然有问题。
（1）对于重复的数字，我们不处理它，可将其任意交换，最后必然会交换到缺失的整数所在的位置；
（2）由于存在将数字 nums[i] 交换到其对应位置时，该位置已被其重复数字 nums[i]' 占据，导致死循环的情况，所以在比较时要注意目标位置上的值是否已经正确；
（3） 注意： 第 i 位被比较并且交换了数值后，此时的 nums[i] 以及是一个新的值了，需要重新判断其对应关系，因此要保证在下一次循环时 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 --;//下一轮继续比较新的 nums[i]
            }
        }
        for (i = 0; i<nums.length;i++) {
            if(nums[i]!= i+1)
                l.add(i + 1);
        }
        return l;
    }