首页 > 代码库 > Leetcode分类刷题答案&心得
Leetcode分类刷题答案&心得
Array
448.找出数组中所有消失的数
要求：整型数组取值为 1 ≤ a[i] ≤ n，n是数组大小，一些元素重复出现，找出[1,n]中没出现的数，实现时时间复杂度为O(n)，并不占额外空间。
思路1：（discuss）用数组下标标记未出现的数，如出现4就把a[3]的数变成负数，当查找时判断a的正负就能获取下标。
tips：注意数组溢出。
public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> disList = new ArrayList<Integer>(); //用数组下标来记录出现过的数 for (int i = 0; i < nums.length; i++) { int item = Math.abs(nums[i]) - 1; //判断是否已经出现过 if (nums[item] > 0) { nums[item] = -nums[item]; } } //把仍然是正数所对应的下标加入数组列表中 for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { disList.add(i + 1); } } return disList; }
思路2：（discuss）下标标记数，但把出现过的数用作下标，然后此下标对应的数+n。
public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> disList = new ArrayList<Integer>(); int n = nums.length; //用数组下标来记录出现过的数 for (int i = 0; i < nums.length; i++) { nums[(nums[i] - 1) % n] += n; } //把a[i]小于n时的i+1加入数组列表中 for (int i = 0; i < nums.length; i++) { if (nums[i] <= n) { disList.add(i + 1); } } return disList; }
思路3：（discuss）整理数组，目的就是把数字与下标对应，整理后下标与数字不对应就证明此数消失。
public List<Integer> findDisappearedNumbers(int[] nums) { for (int i = 0; i < nums.length; i++) { while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) { int tmp = nums[i]; nums[i] = nums[tmp - 1]; nums[tmp - 1] = tmp; } } List<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { res.add(i + 1); } } return res; }
2016-12-14
Leetcode分类刷题答案&心得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。