[LeetCode] 442. Find All Duplicates in an Array

【原题】 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]

【解释】 给定一个含有那个元素的数组, 数组中的元素要么出现一次要么出现两次,要求找出数组中所有的重复元素。 【思路】 因为数组元素的取值都不会越界,且数组只有出现一次和两次良好总可能性,那么可以把书组元素当成是数组的index。循环每次index-1的数乘上-1,若该index-1元素已经为负数,则说明该index之前已经出现过,故必为重复元素,将其加到list即可。

因为这里最多出现两次,所以不需要判断要加入的元素是否会存在list中,刚开始博主就是这样的思想,判断会增加时间复杂度,最终最后一个测试用例不通过,会后换成hashset,再转成list才通过[捂脸]。

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list=new ArrayList<Integer>();
        //HashSet<Integer> hashSet=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            int index=Math.abs(nums[i]);
            if(nums[index-1]<0) //若该index已经为负数,说明前面已经出现过,则这个index肯定是重复的元素
                 list.add(index);
            nums[index-1]*=-1;
        }
        return list;

    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序生活

数据结构-顺序表的定义及python实现

1 顺序表的定义 线性表 是具有相同数据类型的n个数据元素的有限序列。 顺序表 使用组地址连续的存储单元、依次存储线性表中的数据元素,从而使得逻辑上相邻的两...

3245
来自专栏zaking's

用js来实现那些数据结构08(链表02-双向链表)

  其实无论在任何语言中,一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝...

2696
来自专栏java一日一条

Java面试题:栈和队列的实现

(5)设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)

291
来自专栏小二的折腾日记

day5(面向对象2)

为什么出现集合类? 数组是固定长度的,集合是可变长度的。 为什么出现这么多的容器? 因为每一个容器对数据的存储方式都有不同。这个存储方式称之为:数据结构。

643
来自专栏小怪聊职场

Java|Map、List与Set的区别

28612
来自专栏文武兼修ing——机器学习与IC设计

基本2D优先堆基本优先队列二叉堆实现优先队列代码实现

基本优先队列 考虑一种队列:每次取出的数据是队列中最小的元素。这种队列可用于程序调度,作业分配等领域,这种队列被称为优先队列,核心的方法有: Insert()方...

2646
来自专栏苦逼的码农

从零打卡leetcode之day 4--无重复最长字符串

说明:有点抱歉,昨晚发的记得有写题目描述,但不知为啥,题目描述丢失了,可能是自己突然不小心删除了。

733
来自专栏吾爱乐享

java之学习集合的并发修改及案例

1153
来自专栏用户画像

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。

723
来自专栏郭耀华‘s Blog

Java集合框架(三)—— List、ArrayList、Vector、Stack

List接口 List集合代表一个有序集合,集合中每一个元素都有其对应的顺序索引。List集合容许使用重复元素,可以通过索引来访问指定位置的集合对象。 ...

2905

扫码关注云+社区