Leetcode原题
思路
看到題目的時候，给定n个整数的数组，找出数字在区间在【1，n】不存在的数。我的第一反应是可以利用hashmap存储nums 的数。然后再判断[1,n]
范围谁不存在，直接用数组返回就好了。结果题目居然有个要求，不能使用额外的空间，且时间复杂度为O(n).
只能另辟蹊径了。
然后想到了一个办法，由于nums的数字范围都在【1，n】范围内，那么我们可以利用范围以外的数。
我们只需要去遍历获取每个元素num ，num是【1，n】范围内的数。我们只要对其-1 再对n取模得到x.。必然可以取到 【1，n】对应nums[x]值。我们只要将nums[x]修改。那么剩余没有修改到的必然就是[1,n]范围内不存在的数。具体看代码
public List<Integer> findDisappearedNumbers(int[] nums) { int len =nums.length; for(int i=0;i<len;i++){ int tmp= (nums[i]-1)%len; nums[tmp] +=len ; } List<Integer> ret = new ArrayList<Integer>(); for (int i = 0; i <len ; i++) { if(nums[i]<=len){ ret.add(i+1); } } return ret; }
提交记录
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
