当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.442.Find All Duplicates in an Array

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]

解题过程

这道题一看到题干中的1 ≤ a[i] ≤ n,就知道肯定是用数组下标技巧做。
从头开始遍历,对于值a[i],在下标a[i]处将其标记为已存在,但是下标a[i]上原有的值不能被覆盖,那怎么办呢?在这里我着实思考了一会儿,然后发现可以将下标a[i]上的值减去数组a的长度来表示已被标记,非常巧妙:

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<nums.length; i++){
            //有的被标记过的值已经是负的,需要对其进行加nums.length还原
            int realindex = nums[i]>=1 ? nums[i] : nums[i]+nums.length;
            if(nums[realindex-1] >= 1){//下标位nums[i]没有被标记过
                //把下标位nums[i]的值减nums.length,以此来表示此下标位的值存在
                nums[realindex-1] -= nums.length;                
            }else{//已被标记过的值肯定<=0
                list.add(realindex);
            }
        }
        return list;
    }
}

并且满足O(n)时间复杂度且无额外空间开销的要求,速度很快,打败了77%的代码。

提交之后看Discuss,发现一个更简洁的代码,思路相同,但人家是将下标a[i]处的值设为负的来标记,更巧妙:

public class Solution {
    // when find a number i, flip the number at position i-1 to negative. 
    // if the number at position i-1 is already negative, i is the number that occurs twice.

    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;
    }
}

这位大神解释自己的思路时描述的也非常好:

I was thinking we need a way to “hash” the same number together without using extra space. I am inspired by the range of the input value (1 - N), which seems fit the index of the input array (0 - N-1).
If I hash num[i] to index num[i]-1, then I need to store it at index num[i]-1 smartly. I shouldn’t make irrecoverable change to the element at that position, because I may need the element in the future. Again using the given range of input is (1 - N), if flip it to the opposite I can still recover it using Math.abs

这类方法的缺点是只能找到重复的数,但无法知道重复了几次。


GitHub代码


上一篇 LeetCode.136.Single Number

下一篇 LeetCode.725.Split Linked List in Parts

阅读
639
阅读预计3分钟
创建日期 2018-01-21
修改日期 2018-01-23
类别
百度推荐