当前位置: 首页 > >

【刷题1】LeetCode 448. 找到所有数组中消失的数字 java题解

发布时间:


害 自己写的超时了



题目

448. 找到所有数组中消失的数字


分析

第一趟:


第二趟:
元素还为正数的位置(index),对应的数(index+1)就是不存在滴。


代码

class Solution {
public List findDisappearedNumbers(int[] nums) {
ArrayList res=new ArrayList<>();
if(nums==null||nums.length==0)
return res;
for(int i=0;i
//都是为了防止多次取反,因为一个数可能出现多次
int index=Math.abs(nums[i])-1;
if(nums[index]>0)
nums[index]=-nums[index];
}
for(int j=1;j<=nums.length;j++){
//还是正数,说明j对应的数未出现过
if(nums[j-1]>0){
res.add(j);
}
}
return res;
}
}

复杂度

时间复杂度:O(N)。
空间复杂度:O(1),因为我们在原地修改数组,没有使用额外的空间。


结果



友情链接: