当前位置 博文首页 > 一条IT：【leetcode刷题】14.找到所有数组中消失的数字——Java
?欢迎订阅《leetcode》专栏，每日一题，每天进步?
将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。
——leetcode此题热评
哈喽，大家好，我是一条。
糊涂算法，难得糊涂
今天你糊涂了吗？
难度：简单
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]示例 2：
输入：nums = [1,1] 输出：[2]提示：
n == nums.length 1 <= n <= 105 1 <= nums[i] <= n进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
Solution
鸽笼原理
由题意可得，1n的位置表示1n个笼子，如果出现过，相应的“鸽笼”就会被占掉，我们将数字置为负数表示被占掉了。
最后再遍历一遍，如果“鸽笼”为正数就是没出现的数字。
Code
所有
leetcode代码已同步至github欢迎
star/** * @author yitiaoIT */ class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { for (int i = 0; i < nums.length; i++) { nums[Math.abs(nums[i])-1]=-Math.abs(nums[Math.abs(nums[i])-1]); } ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i]>0){ list.add(i+1); } } return list; } }Result
复杂度分析
- 时间复杂度：O(N)
🌈寻宝
?今天是坚持刷题更文的第14/100天
?各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
?更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找，寻宝游戏现在开始。
找不到可以评论留言，一条就会注意到你。
如果还不行，请私信我。
cs
下一篇：没有了
