关关的刷题日记03—Leetcode 448. Find All Numbers Disappeared in an Array

题目

448. Find All Numbers Disappeared in an 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]

题目的意思是长度为n的数组存了1~n范围的整数,有一些数缺失了,有一些数出现了两次,让找到所有缺失的数。

方法1

思路1:设置一个标记数组flag,flag下标对应数组中的数,遍历数组中的数,把对应的下标元素标记为1;再遍历flag,元素值为0的就是缺失的数。 优点是思路简单,时间复杂度低o(n),缺点是需要额外空间。 但是题目要求不能开辟额外空间,所以不满足题目要求。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int>flag(nums.size()+1, 0);
        vector<int>output;
        for(int i=0; i<nums.size(); i++)
            flag[nums[i]]=1;
        for(int i=1; i<=nums.size(); i++)
        {
            if(flag[i]==0)
                output.push_back(i);
        }
        return output;
    }
};

方法2

思路2:将数组进行排序,然后后一个元素减去前一个元素作差,如果差值大于1,就说明此处有缺失元素。不过这种方法虽然不需要额外空间,但是时间复杂度o(nlogn),不满足题目要求。

方法3

思路3:由于题目中有数组中所有数字都大于等于1且小于等于n,而n为数组长度这一条件。所以思路1中不要额外开辟一个标记数组,就用原来的数组自己来标记就行了。将以nums数组元素为下标的数标记为负数,最后遍历,元素值为正数对应的下标值就是缺失元素。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int>output;
        for(int i=0; i<nums.size(); i++)
        {
            int flag=(nums[i]>0?nums[i]:(-nums[i]))-1;
                nums[flag]=(nums[flag]<0?nums[flag]:(-nums[flag]));
        }
        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i]>0)
                output.push_back(i+1);
        }
        return output;
    }
};

点击专知主题Leetcode: http://www.zhuanzhi.ai/#/topic/2001901869867117。查看更多关于关关的Leetcode的刷题日记。

欢迎大家使用专知!点击阅读原文即可访问,访问专知,搜索主题,获取更多关于LeetCode教程资料

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-09-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-137-Single Number II-第二种解法

3.8K12
来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(五)映射

经过了前面四篇文章的学习,相信大家对Stream流已经是相当的熟悉了,同时也掌握了一些高级功能了,如果你之前有阅读过集合框架的基石 Collection 接口,...

942
来自专栏Python

面向对象的三大特性(封装、继承、多态)

继承 什么是继承 继承是一种创建新类的方式,在python中,新建的类可以继承一个或多个父类,父类又可称为基类或超类,新建的类称为派生类或子类 python中类...

1.7K9
来自专栏黑泽君的专栏

HashMap与Hashtable的区别是面试中经常遇到的一个问题。

HashMap与Hashtable的区别是面试中经常遇到的一个问题。这个问题看似简单,但如果深究进去,也能了解到不少知识。本文对两者从来源,特性,算法等多个方面...

2443
来自专栏算法修养

接口和多态性

如果你又加了一个百度外卖,那么eat函数中又要new 一个BaiDu() ,给开发带来麻烦。我们希望的是,如果代码要扩展了,那么代码要尽最大可能的进行很小的改动...

913
来自专栏计算机视觉与深度学习基础

HDU2066

神坑的题目 思路就是枚举起点,迪杰斯特拉求最短路径,再枚举终点(如果起点终点一起枚举可能会超时,也能勉强扯上动态规划的思想吧),求最短路径。 如果剪枝可以加一个...

2327
来自专栏算法channel

程序员必知的算法和数据结构:2500字性能总结

以下5个步骤总结了此方法,依次为如下,我们设计的实验必须是可以重现的,我们形成的假设必须是具有真伪的。

750
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构·队列的链表实现

? 正文之前 今天看无穷级数这个数学内容实在看得头疼,索性看到八点多就不看了。愉快的写起了码,对我来说这个可有趣了!虽然有时候莫名其妙的就会Run succe...

2885
来自专栏Crossin的编程教室

真值表

逻辑判断是编程中极为常用的知识。之前的课我们已经说过,见第6课和第11课。但鉴于逻辑运算的重要性,今天我再把常用的运算结果总结一下,供大家参考。 这种被称为“真...

2364
来自专栏工科狗和生物喵

【计算机本科补全计划】C++牛客网试题习题解析

正文之前 一大早醒来,外面淅淅沥沥的雨绵绵的下着,床铺真的舒服,但是我也不能就在床上刷微博看小说吧,所以想起了昨晚下载的牛客网的APP,赶紧掏出我的大宝贝---...

3857

扫码关注云+社区

领取腾讯云代金券