2019-06-05.md

每日一题 - Find All Numbers Disappeared in an Array

信息卡片

• 时间：2019-06-05
• 题目链接：https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
• tag：array

题目描述

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

参考答案

使用额外的空间记录出现过的数字, 时间复杂度和空间复杂度皆为O(n)

参考代码

/*
 * @lc app=leetcode id=448 lang=javascript
 *
 * [448] Find All Numbers Disappeared in an Array
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    let allNums = [];
    let res = [];

    for (let i = 0; i < nums.length; i++){
        allNums[nums[i] - 1] = true;
    }

    for (let i = 0; i < nums.length; i++){
        if(!allNums[i]){
            res.push(i + 1);
        }
    }
    return res;
};

充分利用题目 "You may assume the returned list does not count as extra space."

• 用res记录哪些数字出现过
• 最后遍历时, 判断res是否为空, 若是, 则证明未出现过, 将其写回res

参考代码

/*
 * @lc app=leetcode id=448 lang=javascript
 *
 * [448] Find All Numbers Disappeared in an Array
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const res = [];
    let cur = 0;
    for(let i = 0; i < nums.length; i++) {
        res[nums[i]] = true;
    }

    for(let i = 0; i < nums.length; i++) {
        if (res[i + 1] === void 0) {
            res[cur++] = i + 1;
        }
    }

    res.length = cur;

    return res;
};

其他优秀解答

利用python集合类型的特点： 元素唯一, 不存在相同元素

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ls = [i for i in range(1, len(nums)+1)]

        return list(set(ls) - set(nums))