[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 条评论
登录 后参与评论

相关文章

来自专栏好好学java的技术栈

“365算法每日学计划”:04打卡-自己动手写一个单链表

1323
来自专栏赵俊的Java专栏

从源码上分析 LinkedList(附图)

1555
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

30812
来自专栏desperate633

LintCode 用递归打印数字题目分析代码

recursion(i) { if i > largest number: return results.add(i) recursion(i + 1)...

551
来自专栏Android开发小工

Java集合解惑

本文取自工匠若水的qq群里的Java基础题目,把里面有关Java集合放在一起。 全文github地址

892
来自专栏奔跑的蛙牛技术博客

集合(2)

我们知道数组和ArrayList有一个重大缺陷。这个缺陷就从数组的中间位置删除一个元素需要付出重大的代价,因为从数组中间删除一个元素,元素中间的位置都需要向前移...

652
来自专栏移动端开发

Java集合类总结

前言: 这篇准备好好总结一下Java的集合类,在顺便带上Arrays,把这几者之间的关系说清楚,在java.util包中提供了一些集合类,这些集合类又被称作容...

2479
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

1786
来自专栏LeetCode

LeetCode 830.Position of Large Group

总结:本题属于双指针的问题,一个标记重复字符串的左,一个标记右,从字符串的头部滑动到尾部,遇到满足一部要求的解后,加入res。

310
来自专栏Ryan Miao

在java中使用redis

在java中使用redis很简单,只需要添加jedist.jar,通过它的api就可以了。而且,api和redis的语法几乎完全相同。以下简单的测试: 参考:h...

5578

扫码关注云+社区