05 August 2008
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:
1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
给一个数组，数组元素的范围在1 ≤ a[i] ≤ n (n = size of array)，找到所有数组中缺少的数，要求O(1)的空间和O(n)的时间复杂度，所以只能在原来的数组上操作了，也不能排序了，有很多种办法可以做：
1） 第一遍循环，对于每个数字nums[i]，我们认为nums[nums[i] - 1]是其对应的数，如果这个对应的数是正数，将其赋值为负数，如果已经是负数，就不变；可以想象，如果某些数1 ≤ a[i] ≤ n 缺失了，那么它们对应的索引处的整数就不会被改变成负数，然后第二遍循环我们就找出剩余的正数，返回这些正数所对应的索引值，就是原本数组中缺少的数字；
2）第一遍循环，将nums[i]交换到其对应的位置索引nums[nums[i]-1]上去，比如题目给的例子例子，如果没有缺失的数你那正确的顺序应该是[1, 2, 3, 4, 5, 6, 7, 8]，现在是[4, 3 ,2 ,7 ,8 ,2 ,3 ,1]，于是把数字移动到正确的位置上去，比如第一个4（nums[0]）就应该和7（nums[4-1] = nums[3]）逐个交换个位置，有点选择排序的思想，最后得到的顺序是[1, 2, 3, 4, 3, 2, 7, 8]，最后在对应位置检查，如果nums[i]和i+1不等，那么将i+1存入结果中即可;
3）对于[4, 3 ,2 ,7 ,8 ,2 ,3 ,1]，在nums[nums[i]-1]位置累加数组长度len，(nums[i]-1有可能越界，所以需要对len取余)，最后要找出缺失的数只需要看nums[i]的值是否小于等于len即可，最后遍历完nums[i]数组为[12, 19, 18, 15, 8, 2, 11, 9]，我们发现有两个数字8和2小于等于len，那么就可以通过i+1来得到正确的结果5和6了;
正负数来标记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList();
if (nums == null || nums.length == 0) {
return result;
}
int len = nums.length;
//先把元素对应的索引处改为负数
for (int i = 0; i < len; i++) {
int index = Math.abs(nums[i]) - 1;
nums[index] = (nums[index] > 0) ? -nums[index] : nums[index];
}
//找到目前剩余的正数，返回索引值
for (int i = 0; i < len; i++) {
if (nums[i] > 0) {
result.add(i + 1);
}
}
return result;
}
}
交换索引和数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList();
if (nums == null || nums.length == 0) {
return result;
}
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] != nums[nums[i] - 1]) {//相等则说明刚才已经交换过了
swap (nums, i, nums[i] - 1);//将i位置的元素和nums[i] - 1处的元素进行交换，放在合适的位置
i--;//交换后需要在当前位置停留一下检查当前元素的交换位置
}
}
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
result.add(i + 1);
}
}
return result;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
累加数组长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList();
if (nums == null || nums.length == 0) {
return result;
}
int len = nums.length;
for (int i = 0; i < len; i++) {
nums[(nums[i] - 1) % len] += len;
}
for (int i = 0; i < len; i++) {
if (nums[i] <= len) {
result.add(i + 1);
}
}
return result;
}
}