題目:給一個數(shù)組及老,里面的數(shù)字是從1到數(shù)組長度的數(shù)組抽莱,有重復,找出那些屬于1到數(shù)組長度的沒有出現(xiàn)在數(shù)組里的數(shù)。
解題思路:先將數(shù)組排序斟叼,先分兩種情況,如果nums[0]大于1,則循環(huán)加入從2到nums[0]-1的數(shù)字,如果nums[nums.length-1]大于nums.length,則循環(huán)加入之間的數(shù)字,中間的皆的,如果num[i]!=nums[i+1]+1,則循環(huán)加入之間的數(shù)字,這算是笨辦法,寫完以后accepted召廷。等會看答案順便更新厲害的解決辦法治泥,我的代碼:
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
Arrays.sort(nums);
int interval=0;
List<Integer> result=new ArrayList<Integer>();
for(int i=0;i<nums.length-1;i++){
if(i==nums.length-2 && nums[i+1]<nums.length){
for(int j=nums[i+1]+1;j<=nums.length;j++)result.add(j);
}
if(nums[i]!=nums[i+1]+1){
for(int j=nums[i]+1;j<nums[i+1];j++)result.add(j);
}
if(nums[i]>1 && i==0){
for(int j=1;j<nums[0];j++)result.add(j);
}
}
return result;
}
}
看了一會厲害的代碼本冲,這個題目應該是沒什么取巧的方法粟关,那個人的代碼意思是循環(huán)一邊將nums里的數(shù)字只要出現(xiàn)過的就將這個數(shù)字對應的數(shù)組里的位置數(shù)字置為負數(shù),循環(huán)第二遍的時候?qū)?shù)字不是負數(shù)的數(shù)組下標+1添加到List里面性昭,代碼:
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
for(int i = 0; i < nums.length; i++) {
int val = Math.abs(nums[i]) - 1;
if(nums[val] > 0) {
nums[val] = -nums[val];
}
}
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
ret.add(i+1);
}
}
return ret;
}