刷题6：热题100

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] dpleft = new int[nums.length];
        int[] dpright = new int[nums.length];
        int[] answer = new int[nums.length];
        dpleft[0] = 1;
        dpright[nums.length-1] = 1;
        for (int i=1;i<nums.length;i++){
            dpleft[i] = dpleft[i-1]*nums[i-1];
        }
        for (int i=nums.length-2;i>=0;i--){
            dpright[i] = dpright[i+1]*nums[i+1];
        }
        for (int i=0;i<nums.length;i++){
            answer[i] = dpleft[i] * dpright[i];
        }
        return answer;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        //最小正整数只能在【1，nums.length+1】中间出现
        //将数组当成map看待

        // 给每一个负数元素打上标记：只要是不影响后面的标记就行，可以大于等于nums.length+1
        for (int i=0;i<nums.length;i++){
            if (nums[i]<=0){
                nums[i] = nums.length+1;
            }
        }
        // 给数组中在【1，nums.length】区间的元素打上标记
        // 每个数组（i）下标+1，代表正整数（i+1）
        // 如果有i+1的值的正整数，则下标i的数组元素打为负数
        for (int i=0;i<nums.length;i++){
            int num = Math.abs(nums[i]);
            if (num<=nums.length){
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }
        // 找到第一个不为负数的元素，记住下标i，则i+1即未不存在的正整数
        for (int i=0;i<nums.length;i++){
            if (nums[i]>0){
                return i+1;
            }
        }
        // 如果【1，nums.length】都具有，即下标【0，nums.length-1】元素都打了标记
        // 则返回之后的下一个正整数
        return nums.length+1;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 置换元素，匹配正整数和元素下标

        // 找到在区间【1，nums.length】的元素，将该元素与下标相对应的元素交换
        for (int i=0;i<nums.length;i++){
            while(nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1]!=nums[i]){
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }
        }
        // 找到置换之后的数组中，元素与下标不符合的第一个下标，即为最小正整数-1
        for (int i=0;i<nums.length;i++){
            if (nums[i]!= i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }
}