leetcode442. Find All Duplicates in an Array

yimo 发布于2019-08-16 18:27 / 3296人阅读

摘要：题目要求存在一个整数数组，其中的所有元素都位于之间，其中是数组的长度。有的元素出现了一次，而有的元素出现了两次。思路一交换为了在的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。

题目要求

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]

存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。

思路一：交换

为了在O(N)的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。思路一采用交换的核心思想，即每次都将当前下标上的值和以该值为下标的位置上的值进行交换，如果该值下标位置上的值和其相等，则说明该数字已经被遍历过一遍了。

代码如下：

    public List findDuplicates(int[] nums) {
        int index = 0;
        List result = new ArrayList();
        while(index < nums.length) {
            int num = nums[index];
            if(num == 0){
                index++;
            }else if (nums[num-1] == num) {
                if(index != num-1){
                    result.add(num);
                    nums[index] = 0;
                }
                index++;
            }else{
                swap(index, num-1, nums);
            }
        }
        return result;
    }
    
    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

思路二：取反

有没有一种办法在既保留当前位置上的值nums[i]的同时，又能够用某种方式记录i+1是否已经被访问过了？可以通过取反的方法来记录是否被访问过这个情况。如果访问到下标为i的位置上的值，则去判断nums[nums[i]-1]位置上的值是否为负数，如果是，则说明num[i]出现了两次，否则将nums[nums[i]-1]位置上的值取反保留。

代码如下：

    public List findDuplicates(int[] nums) {
        List res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }

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

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

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

[LeetCode] 442. Find All Duplicates in an Array

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 ...

liukai90 2019-08-16 14:28 评论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