|
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
第一种时间复杂度为O(2n)解法：
假设有一个从1~n的数字，新建一个数组长度为给定数组两倍的数组，然后拼接到后面循环处理，把数值存储到list中，记录第一个数组存储到list最后的位置，然后从这个位置分隔list，剩下的list的值就是结果
public List<Integer> findDisappearedNumbers(int[] nums) {
if (nums == null) {
return null;
}
int length = nums.length;
int[] maxNums = new int[2 * length];
//从1开始
int start = 1;
int bucket = 0;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < maxNums.length; i++) {
if (i < length && !list.contains(nums[i])) {
list.add(nums[i]);
bucket++;
}
if (i >= length) {
if(!list.contains(start)){
list.add(start);
}
start++;
}
}
list = list.subList(bucket, list.size());
return list;
}
正确解法：
/**
* 1.其实就是两个数组比较 另一个隐藏的数据就是1~给定数组的长度
* 两个数组合并成一个 隐藏的数组拼接到后面 但此时时间复杂度为O(2n)
* 2.可以将对应的数字nums[i]交换到对应数字的索引处 就是数字4应该交换到数组中的索引为3的位置处
* 数组从0开始 所以和数组中数字-1的索引的位置的数字比较 数组从1开始，所以可以这样做，无需考虑交换时数组越界。
*
* @param nums
* @return
*/
public List<Integer> findDisappearedNumbers(int[] nums) {
if (nums == null) {
return null;
}
int length = nums.length;
List<Integer> list = new ArrayList<>();
int temp;
for (int i = 0; i < length; i++) {
if (nums[i]!=nums[nums[i]-1]){
temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
i--;
}
}
System.out.println(Arrays.toString(nums));
for (int i = 0; i < length; i++) {
if(nums[i]!= (i+1)){
list.add(i+1);
}
}
list.stream().forEach(num -> {
System.out.println("num:" + num);
});
return list;
}
| 
转播
