找到所有數(shù)組中消失的數(shù)字
題目
給定一個范圍在 1 ≤ a[i] ≤ n (n = 數(shù)組大小 ) 的 整型數(shù)組惶翻，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次啦膜。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字漠另。
您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)焕檬。
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處膏蚓。
思路
題目本意不難,因為只要將數(shù)組遍歷然后排序,之后再次遍歷即可.這樣就滿足了O(n)的時間復雜度.難點在于不適用額外的空間,也就是交換時只能基于原有數(shù)組進行交換
代碼
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
//對原有數(shù)組進行比較交換,將當前數(shù)字應該在的位置與被占有位置進行交換.屆時只需比較位置上的值與索引是否相等即可.
for(int i = 0;i < nums.length;i++){
while(nums[nums[i] -1] != nums[i]){
swap(i,nums[i]-1,nums);
}
}
for(int i =0;i < nums.length;i++){
if(nums[i] != i+1){
result.add(i+1);
}
}
return result;
}
//難點在于不使用額外的空間,因此交換使用^來進行
public void swap(int i,int y,int[] nums){
if(i == y){
return;
}
nums[i] = nums[i] ^ nums[y];
nums[y] = nums[i] ^ nums[y];
nums[i] = nums[i] ^ nums[y];
}
}
