[LeetCode] 442. Find All Duplicates in an Array

liukai90 发布于2019-08-16 14:28 / 1584人阅读

Problem

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]

Solution

class Solution {
    public List findDuplicates(int[] nums) {
        //use index to record visited: times -1
        List res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = nums[i] > 0 ? nums[i]-1 : -nums[i]-1;
            if (nums[index] < 0) res.add(index+1);
            nums[index] *= -1;
        }
        return res;
    }
}

云服务器 GPU云服务器 array_find FIND_IN_SET in_array() in_array

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73016.html

leetcode442. Find All Duplicates in an Array

摘要：题目要求存在一个整数数组，其中的所有元素都位于之间，其中是数组的长度。有的元素出现了一次，而有的元素出现了两次。思路一交换为了在的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。题目要求 Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some e...

yimo 2019-08-16 18:27 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LeetCode] 491. Increasing Subsequences

Problem Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example: ...

wupengyu 2019-08-16 13:50 评论0 收藏0
[Leetcode] Contains Duplicate 包含重复

摘要：代码集合法复杂度时间空间思路同样使用集合，但这次我们要维护集合的大小不超过，相当于是记录一个宽度为的窗口中出现过的数字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

rozbo 2019-08-14 12:28 评论0 收藏0
leetcode217.219.220 contains duplicate

摘要：输入一个整数数组，查看数组中是否存在重复的值。新的数组中数组的下标为原数组的值，如果遍历过，则设置为。这里使用了作为实现的数据结构，通过堆的形式对集合中的数据进行存储，从而我们可以通过某种顺序获得该集合中的所有顺序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...

tulayang 2019-08-16 10:56 评论0 收藏0