本文主要是介绍LeetCode Find All Duplicates in Array and Find Disappeared Numbers in Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
lz这里把leetcode中相同类型的两题放在一起来研究。首先是leetcode find all duplicates in array，题目如下：
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input: [4,3,2,7,8,2,3,1]Output: [2,3]给定一个数组，其中数组中的元素从1到n，有些元素只出现一次，有些元素出现了两次，要求找出出现重复的元素。并且要求时间复杂度为 O( n )，空间复杂度为0。此题既然要求不能另开数组空间，且时间复杂度为O(n)，那么只能采用巧妙的方法。考虑这些元素只出现一次或两次，所以利用下标和位置元素来重新标记。从数组头开始向后进行扫描，碰到这个数组的当前位置，那么考虑此元素远来应该在那个位置的元素，如果那个位置的元素为正，那就把它置为负；如果为正，那么说明，已经是第二次了，即重现了重复，直接将它放入list中。
public class findDuplicates
{public List<Integer> findDuplicates(int[] nums){List<Integer> list = new ArrayList<>();int length = nums.length;if(length == 0)return list;for(int i = 0; i < length; i++){if(nums[Math.abs(nums[i]) - 1] > 0)nums[Math.abs(nums[i]) - 1] = -1 * nums[Math.abs(nums[i]) - 1];elselist.add(Math.abs(nums[i])); //直接放入list中}return list;}
}另一题，找出缺失的数，即上一题的相反，题目如下：
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input: [4,3,2,7,8,2,3,1]Output: [5,6]
题目背景与上一题一样，只是这次需要求缺失的数，那么用同样的方法来做，只是，现在当扫描到当前位置的数为负，则跳过，不再保存进list中，然后再扫描一遍数组，找出那些数组元素为正的位置下标，即为缺失的数，将其保存进list即可。
public class findDisappearedNumbers
{public static List<Integer> findDisappearedNumbers(int[] nums){int length = nums.length;List<Integer> list = new ArrayList<>();if(length == 0)return list;for(int i = 0; i < length; i++){if(nums[Math.abs(nums[i]) - 1] > 0)nums[Math.abs(nums[i]) - 1] = -1 * nums[Math.abs(nums[i]) - 1];elsecontinue; //碰到是正，直接跳过}for(int j = 0; j < length; j++) //再次扫描一遍数组，将数组元素为正的下标+1即为缺失的数{if(nums[j] > 0)list.add(j + 1);}return list;}
}
这篇关于LeetCode Find All Duplicates in Array and Find Disappeared Numbers in Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
