[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 HashSet 去除重复值原理

Java中的set是一个不包含重复元素的集合,确切地说,是不包含e1.equals(e2)的元素对。Set中允许添加null。Set不能保证集合里元素的顺序。

2921
来自专栏皮皮之路

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

32612
来自专栏java一日一条

如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

781
来自专栏LeetCode

LeetCode 830.Position of Large Group

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

490
来自专栏我是业余自学C/C++的

Remove Duplicates from Sorted Array II

1744
来自专栏杨熹的专栏

【LEETCODE】模拟面试-39. Combination Sum

和subset区别:规定了子集的sum==target 注意,这里传递的起始位置是i,而不是position+1,but why??? helper(res, ...

2895
来自专栏皮皮之路

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

1443
来自专栏Android开发小工

Java集合解惑

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

1342
来自专栏Ryan Miao

在java中使用redis

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

6528
来自专栏Bingo的深度学习杂货店

Q67 Add Binary

Given two binary strings, return their sum (also a binary string). For example, ...

2888

扫码关注云+社区

领取腾讯云代金券