leetcode-17.19-消失的两个数字

链接：https://leetcode.cn/problems/missing-two-lcci/

难度：困难

problem

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示：nums.length <= 30000

solution

DP

先给原数组排序，再对排序完的数组进行判断是否存在缺失数字，如果存在就push进res数组直到res数组满了，如果不存在就往两边搜索。

求差集

时间复杂度和空间复杂度都比较高。

code

DP

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var missingTwo = function(nums) {
    // 先对于nums做升序排序
    let sortedNums = nums.sort(function(a, b) {
        return a - b;
    });

    let sortedNumsLen = sortedNums.length;

    // 返回值
    let res = [];

    // 扫描sortedNums中是否存在缺的数字
    for (let i = 0; i < sortedNums.length - 1; i++) {
        let cur = sortedNums[i];
        let next = sortedNums[i+1];
        if (cur + 1 !== next) {
            res.push(cur+1);
        }

    }

    // 如果仍然有缺失的数字则往两边搜索
    // 向左搜索
    if (res.length < 2) {
        let head = sortedNums[0];

        for (let i = 0; i < head - 1; i++) {
            res.push(i + 1);
        }
    }

    // 向右搜索
    if (res.length < 2) {
        let tail = sortedNums[sortedNumsLen - 1];

        // 这里需要保存一下res.length当前的值，因为for循环体内改变了res.length
        let resLen = res.length;
        for (let i = 0; i < (2 - resLen); i++) {
            res.push(tail + i + 1);
        }
    }

    return res;
};

求差集

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var missingTwo = function(nums) {
    // 先对于nums做升序排序
    let sortedNums = nums.sort(function(a, b) {
        return a - b;
    });

    let sortedNumsLen = sortedNums.length;
    let correctNums = new Array(sortedNumsLen+2);

    // 填充对照的数组
    for (let i = 0, len = correctNums.length; i < len; i++) {
        correctNums[i] = i + 1;
    }

    let sortedNumsSet = new Set(sortedNums);
    let correctNumsSet = new Set(correctNums);
    let res = [];

    for (let item of correctNums) {
        if (!sortedNumsSet.has(item)) {
            res.push(item);
        }
    }

    return res;
};

trap

向右搜索的for循环应该先保存一下res.length（见代码）。