leetcode442. Find All Duplicates in an Array

栏目: 编程工具 · 发布时间: 6年前

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

题目要求

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<Integer> findDuplicates(int[] nums) {
        int index = 0;
        List<Integer> result = new ArrayList<Integer>();
        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<Integer> findDuplicates(int[] nums) {
        List<Integer> 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;
    }

以上所述就是小编给大家介绍的《leetcode442. Find All Duplicates in an Array》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

一路编程

一路编程

史蒂夫·富特 (Steven Foote) / 佟达 / 电子工业出版社 / 2017-1-1 / CNY 65.00

《一路编程》是一本编程入门书籍,然而,如果以书中所讲内容作为入门标准,估计十有八九的在职程序员都不能算已入门。现代软件开发,已经不仅仅是写出正确的代码这么简单,环境、依赖、构建、版本、测试及文档,每一项都对软件是否成功交付起到至关重要的作用,这些都是每一个程序员在开发软件过程中必备的技能。《一路编程》对于上述的每一种技能都做了简洁而精练的介绍,以满足最基本的日常软件开发。换句话说,《一路编程》实际......一起来看看 《一路编程》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具