抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

Java 原地哈希

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* 原地哈希
* <p>
* 1 2 3 4 3 2 7 8
*
* 1-n之间
*
* @param nums
* @return
*/
public List<Integer> findDisappearedNumbers(int[] nums) {
//4, 3, 2, 7, 8, 2, 3, 1
int len = nums.length;
int index = 0;
while (index < len ) {
if (nums[index] == index + 1) {
index++;
} else {
int targetIndex = nums[index] - 1;
//若目标数等于下标数则不需要进行转换, 进入下一个数
if (nums[targetIndex] == nums[index]) {
index++;
continue;
}
//若否则进行换数
int temp = nums[targetIndex];
nums[targetIndex] = nums[index];
nums[index] = temp;
}

}

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

System.out.println(Arrays.toString(nums));

for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
res.add(i + 1);
}
}

return res;
}

自己简单写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int[] array = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
array[nums[i]] = 1;
}

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

for (int i = 1; i < array.length; i++) {
if (array[i] == 0) {
list.add(i);
}
}

return list;
}
}

用户交流区

温馨提示: 遵纪守法, 友善评论!





津ICP备19009605号

WordCount27.3k