LeetCode 442题

leetcode 442.

题目要求：

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?

翻译：一个整形数组，数值范围为1 ≤ a[i] ≤ n （数组的长度为n），数组中有某些数值出现了两次，其他的只出现一次。请找出数组中出现过两次的所有数值。

注意，时间复杂度限制为O(n)，并且不能申请额外的空间。

输入输出示例：

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

Output:[2,3]

解题思路：

纯粹的遍历，时间复杂度将达到O(n2)，所以要考虑使用一些技巧，把一个无序的数组转换成有规律可循的数组。

思考之后，每一个数值跟数组的长度都是同样的取值范围，那么可以对应起来。

只需要进行一遍遍历，当取出一个数值时，去它对应的数组位置的数字进行标记，如果是第一次则把对应位置的数字标记为负，如果是已经为负，那么这就是一个重复的值。

此时可以把这个值放入结果list中。

有点需要注意的是，数值范围是1-n，而数组长度范围是0-（n-1）。所以在对应的时候要减一操作。

Java代码的实现：

public class Solution {

public List<Integer> findDuplicates(int[] nums) {

List<Integer> result = new ArrayList<Integer>();

for(int i = 0; i < nums.length; i++)

{

if((nums[Math.abs(nums[i])-1] < 0) && !result.contains(Math.abs(nums[i])))

result.add(Math.abs(nums[i]));

else if(nums[Math.abs(nums[i])-1] > 0)

nums[Math.abs(nums[i])-1] *= -1;

}

return result;

}

}