p448

发表于 | 分类于 |

LeetCode p448 Find All Numbers Disappeared in an Array 题解

1.题目：

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

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

Output:
[5,6]

题意：

输入一个长度为n的数组，其中每个数可以出现一次或者一次以上。
输出所有一次都没有出现过的数。

2.解题思路:

第一次循环，将出现过的数对应位置上的值标记为负。
第二次循环筛选出所有为正的位置。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ansList = new ArrayList();
		int n = nums.length;

		Arrays.sort(nums);
		for (int i = 0; i < n; i++) {

			int a = Math.abs(nums[i]) - 1;
			
			nums[a] = -Math.abs(nums[a]);
		}
		for (int i = 0; i < n; i++) {

			if (nums[i] > 0)
				ansList.add(i + 1);
		}
		return ansList;
    }
}

4.一些总结：