448. Find All Numbers Disappeared in an Array(找到所有数组中消失的数字)
448. Find All Numbers Disappeared in an Array(找到所有数组中消失的数字)
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]给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]思路： 假设原数组是nums[0]=0,nums[1]=1...的有序的桶数组，现在的题目可以想象成，把其中一些桶里面的数字改掉，nums[5]不等于5，改为2，nums[6]不等于6，改为3，接着将这个数组元素打乱顺序，然后问，有哪些数字被修改了没出现过。
遍历数组元素，将每个桶里的元素还原，比如找到0，就标记0号桶，说明0元素出现过，货真价实没被篡改，出现1就标记1号桶，这个元素出现了没被篡改。可以通过标记对应下标的桶为负，说明这个桶里的数字出现了，没被篡改。将所有的数组遍历之后，没被标记的桶对应的数字被篡改了，也就是没出现的。
代码如下：
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums.length; ++i) {
int j = Math.abs(nums[i]) - 1; // 假设nums[0] = 0, nums[1] = 1...找到桶下标
if (nums[j] > 0) { // 标记对应下标的桶为负，说明这个桶里的数字出现了，没被篡改
nums[j] = -nums[j];
}
}
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > 0) { // 将所有的数组遍历之后，没被标记的说明被篡改了，也就是没出现的
list.add(i + 1);
}
}
return list;
}
}迅雷的笔试题1，采用了leetcode的原题，但是这个答案在leetcode上能AC，但是迅雷笔试却只AC了20%，估计有赛码做题网站的测试点不对。
Debug code in playground
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums.length; ++i) {
int j = Math.abs(nums[i]) - 1;
if (nums[j] > 0) {
nums[j] = -nums[j];
}
}
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > 0) {
list.add(i + 1);
}
}
return list;
}
}
public class MainClass {
public static int[] stringToIntegerArray(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return new int[0];
}
String[] parts = input.split(",");
int[] output = new int[parts.length];
for(int index = 0; index < parts.length; index++) {
String part = parts[index].trim();
output[index] = Integer.parseInt(part);
}
return output;
}
public static String integerArrayListToString(List<Integer> nums, int length) {
if (length == 0) {
return "[]";
}
String result = "";
for(int index = 0; index < length; index++) {
Integer number = nums.get(index);
result += Integer.toString(number) + ", ";
}
return "[" + result.substring(0, result.length() - 2) + "]";
}
public static String integerArrayListToString(List<Integer> nums) {
return integerArrayListToString(nums, nums.size());
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
int[] nums = stringToIntegerArray(line);
List<Integer> ret = new Solution().findDisappearedNumbers(nums);
String out = integerArrayListToString(ret);
System.out.print(out);
}
}
}