热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

leetcode算法:FindAllDuplicatesinanArray

Givenanarrayofintegers,1≤a[i]≤n(nsizeofarray),someelementsappeartwiceandothersappearonce.F

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

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

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

Output:
[2,3]


这道题描述的是:
给我们一个 长度为n 的列表,里面全都是整数 并且满足每个整数都是1到n之间的数

我们要做的是: 找到里面出现两次的整数

要求我们 使用O(n) 的时间复杂度和 O(1)的空间复杂度


描述一下思想:
  这道题困扰了我很久,在网上查阅了一些代码,用了一些时间才搞懂。
  O(n) 的时间复杂度 只允许一次遍历,就找到出现2次的元素
  O(1) 的空间复杂度,我们不能开辟线性空间。
  
  参考了网上大神的代码,他的想法是,把原本给我们的数组,当作hash来做散列映射。具体的做法是这样:
  对一个数组 A = [X,X,X,X,X,X]
    从头开始遍历,对每个元素 i :
      如果 A[ 绝对值(i)-1 ] >0: 我们就让 A[ 绝对值(i)-1 ] = -A[ 绝对值(i)-1 ]
      如果 A[ 绝对值(i)-1 ] <0: 绝对值(i)就是第二次出现&#xff0c;我们把它追加到结果列表
    返回 结果列表

  为什么这样就行呢&#xff1a;
    1 列表长度是n&#xff0c;并且没个元素都是 1到n之间的数&#xff0c;所以 任何一个元素i &#xff0c;用 绝对值(i) - 1 作下标&#xff0c;不会越界
    2 初始情况下&#xff0c;数组每个元素都是正数(1到n之间) , 我们遍历数组&#xff1a;
      每当第一次拿到一个数i&#xff0c;把 A[绝对值(i)-1] 该为负数,(i这个数值第一次出现&#xff0c;响应位置上的数字一定是正数&#xff0c;我们把他改成了负数)
      如果我们拿到一个数i&#xff0c;这个数值是第二次出现&#xff0c;我们在取 A[绝对值(i)-1] 的时候&#xff0c;之前我们就把他改为负数了&#xff0c;所以&#xff0c; 绝对值(i) 这个数&#xff0c;这一次取到 一定是重复的。
        把这个重复的数放到结果列表里
    3 为什么 我们把里面的数字 取相反数&#xff0c;不做其他标记呢&#xff1f; 因为里面数字取相反数 我们还能用绝对值找到原来的数。这里每一个数在我们做映射算法的时候&#xff0c;会依据这个数找到一个数组的位置&#xff0c;所以不能用其他标记。
      



我的python代码&#xff1a;

1 class Solution(object):
2 def findDuplicates(self, nums):
3 """
4 :type nums: List[int]
5 :rtype: List[int]
6 """
7 res &#61; []
8 for i in nums:
9 if nums[abs(i)-1] > 0:
10 nums[abs(i)-1] *&#61; -1
11 else :
12 res.append(abs(i))
13 return res
14
15
16 if __name__ &#61;&#61; &#39;__main__&#39;:
17 s &#61; Solution()
18 res &#61; s.findDuplicates([4, 3, 2, 7, 8, 2, 3, 1])
19 print(res)

 

转:https://www.cnblogs.com/Lin-Yi/p/7905425.html



推荐阅读
  • 微软头条实习生分享深度学习自学指南
    本文介绍了一位微软头条实习生自学深度学习的经验分享,包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性,并提供了一些建议。 ... [详细]
  • 计算机存储系统的层次结构及其优势
    本文介绍了计算机存储系统的层次结构,包括高速缓存、主存储器和辅助存储器三个层次。通过分层存储数据可以提高程序的执行效率。计算机存储系统的层次结构将各种不同存储容量、存取速度和价格的存储器有机组合成整体,形成可寻址存储空间比主存储器空间大得多的存储整体。由于辅助存储器容量大、价格低,使得整体存储系统的平均价格降低。同时,高速缓存的存取速度可以和CPU的工作速度相匹配,进一步提高程序执行效率。 ... [详细]
  • 阿里Treebased Deep Match(TDM) 学习笔记及技术发展回顾
    本文介绍了阿里Treebased Deep Match(TDM)的学习笔记,同时回顾了工业界技术发展的几代演进。从基于统计的启发式规则方法到基于内积模型的向量检索方法,再到引入复杂深度学习模型的下一代匹配技术。文章详细解释了基于统计的启发式规则方法和基于内积模型的向量检索方法的原理和应用,并介绍了TDM的背景和优势。最后,文章提到了向量距离和基于向量聚类的索引结构对于加速匹配效率的作用。本文对于理解TDM的学习过程和了解匹配技术的发展具有重要意义。 ... [详细]
  • 学习SLAM的女生,很酷
    本文介绍了学习SLAM的女生的故事,她们选择SLAM作为研究方向,面临各种学习挑战,但坚持不懈,最终获得成功。文章鼓励未来想走科研道路的女生勇敢追求自己的梦想,同时提到了一位正在英国攻读硕士学位的女生与SLAM结缘的经历。 ... [详细]
  • 向QTextEdit拖放文件的方法及实现步骤
    本文介绍了在使用QTextEdit时如何实现拖放文件的功能,包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数,并结合QMimeData和QUrl等类,可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]
  • 目录实现效果:实现环境实现方法一:基本思路主要代码JavaScript代码总结方法二主要代码总结方法三基本思路主要代码JavaScriptHTML总结实 ... [详细]
  • CSS3选择器的使用方法详解,提高Web开发效率和精准度
    本文详细介绍了CSS3新增的选择器方法,包括属性选择器的使用。通过CSS3选择器,可以提高Web开发的效率和精准度,使得查找元素更加方便和快捷。同时,本文还对属性选择器的各种用法进行了详细解释,并给出了相应的代码示例。通过学习本文,读者可以更好地掌握CSS3选择器的使用方法,提升自己的Web开发能力。 ... [详细]
  • 本文介绍了PhysioNet网站提供的生理信号处理工具箱WFDB Toolbox for Matlab的安装和使用方法。通过下载并添加到Matlab路径中或直接在Matlab中输入相关内容,即可完成安装。该工具箱提供了一系列函数,可以方便地处理生理信号数据。详细的安装和使用方法可以参考本文内容。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • 本文详细介绍了PHP中与URL处理相关的三个函数:http_build_query、parse_str和查询字符串的解析。通过示例和语法说明,讲解了这些函数的使用方法和作用,帮助读者更好地理解和应用。 ... [详细]
  • 本文介绍了C#中数据集DataSet对象的使用及相关方法详解,包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成,以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读,读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]
  • 本文介绍了Perl的测试框架Test::Base,它是一个数据驱动的测试框架,可以自动进行单元测试,省去手工编写测试程序的麻烦。与Test::More完全兼容,使用方法简单。以plural函数为例,展示了Test::Base的使用方法。 ... [详细]
  • Android JSON基础,音视频开发进阶指南目录
    Array里面的对象数据是有序的,json字符串最外层是方括号的,方括号:[]解析jsonArray代码try{json字符串最外层是 ... [详细]
  • 开发笔记:计网局域网:NAT 是如何工作的?
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了计网-局域网:NAT是如何工作的?相关的知识,希望对你有一定的参考价值。 ... [详细]
author-avatar
灵绾绾
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有