[LeetCode]-442. Find All Duplicates in an Array

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:

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

思路

最初思路：这道题看似不难，最初的思路也想的比较简单，就是把数组先排序一波，然后比较前后如果有相同的数就add到结果集合中，但是要满足O（n）的时间复杂度，这里因为没有考虑到数组排序（调用了库，所以忽略了）的时间复杂度，开始是自以为满足了的，但是提交了结果后发现时间复杂度很差。

我的代码

public class Solution {


	public static void main(String[] args) {
		int[] nums = { 4,3,2,7,8,2,3,1 };
		System.out.println(findDuplicates(nums));
	}
	public static List<Integer> findDuplicates(int[] nums) {
		Arrays.sort(nums);
		List<Integer> result = new ArrayList<>();
		for (int i = 0; i < nums.length -1; i++) {
			if(nums[i] == nums[i+1])
				result.add(nums[i]);
		}
		return result;
        }
}

大神的代码

class Solution2 {
	    // solution2
	    public List<Integer> findDuplicates(int[] nums) {
	        List<Integer> ret = new ArrayList<>();
	        for (int i = 0; i < nums.length; i++) {
	            int index = Math.abs(nums[i]) - 1;
	            if (nums[index] < 0) {	//表示前面已经出现过一次了。
	                ret.add(index + 1);
	            }
	            nums[index] = -nums[index];
	        }
	        return ret;
	    }
	}

遇到的问题

1.调用array库中的sort函数时，没有算进自己写的程序的时间复杂度中，导致自己写的程序时间复杂度较大。这里注意，要解决在时间复杂度O(N)内以及不利用额外的space必须要运用的题目中的条件1 ≤ a[i] ≤ n (n = size of array),，这是个很关键的条件。

对比思考

1.大神的代码，想法很好，好好学习！