:-: 2.2 错误的集合 * * * * * **题干：** 集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 示例 1: ~~~ 输入: nums = [1,2,2,4] 输出: [2,3] ~~~ 注意: 1、给定数组的长度范围是 [2, 10000]。 2、给定的数组是无序的。 **题目分析：** 题目分析可得，数组中的值是1~n的整数，如果没有发生错误的话，且经过排序，则它的值和位置的关系是nums[i] = i + 1，我们可以从这个切入点下手，最容易想的，就是暴力破解，还可以从值与位置的对应关系，发生错误后，值与位置的对应关系就被破环。 **新手有可能遇到的解题思路陷阱：** 使用暴力破解，不思考从值与位置的对应关系入手解决这个问题。 **解题思路分析以及代码实现：** 第一种思路：暴力破解。先两层循环找出重复值（错误值），再两层循环找出值与位置不对应的位置加1就是（被替换值）。 第一种思路代码： ~~~ public int[] findErrorNums(int[] nums) { int num[] = new int[2]; for (int i = 0; i < nums.length; i++) { boolean f = false; for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { num[0] = nums[i]; } } for (int j = 0; j < nums.length; j++) { if (nums[j] == i + 1) { f = true; } } if (!f) { num[1] = i + 1; } } return num; } ~~~ **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第二种思路：排序后（排序是根据值与位置的对应关系来排序）遍历找出，与当前值与位置关系不符合的重复值以及被替换的值。 第二种思路代码： ~~~ private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } public int[] findErrorNums(int[] nums) { for (int i = 0; i < nums.length; i++) { while (nums[nums[i] - 1] != nums[i]) { swap(nums, i, nums[i] - 1); } } for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) return new int[] { nums[i], i + 1 }; } return null; } ~~~ **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第三种思路：偷梁换柱。不经过多层循环排序，而是根据值与位置的对应关系，使得错误的数组再另外一个数组上有序，如果值重复在新的数组上对应的位置是相同的，从而造成被替换值的位置是空的，所以我们找出集合中为空的位置，再根据值与位置的对应关系算出被替换值。此为空间换时间。 第三种思路代码： ~~~ public int[] findErrorNums(int[] nums) { int[] count = new int[nums.length]; int[] array = new int[2]; for (int i = 0; i < nums.length; i++) { count[nums[i] - 1]++; } for (int i = 0; i < count.length; i++) { if (count[i] == 2) { array[0] = i + 1; } if (count[i] == 0) { array[1] = i + 1; } } return array; } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第三种思路变种：移形换影。创建另外的一个数组为boolean类型，根据值与位置的对应关系，用值代替位置（舍弃0位置，减少循环中的减运算），将值对应的位置设为true,重复值会对应同一位置，如若此位置的值已经是true，则此为重复值，最后再次遍历新数组（从1开始），如果某个值为false，则此处位置值就是被替换的值。 第三种思路变种代码： ~~~ public int[] findErrorNums(int[] nums) { int[] result = new int[2]; boolean[] array = new boolean[nums.length + 1]; for (int num : nums) { if (array[num]) result[0] = num; array[num] = true; } for (int i = 1; i < array.length; i++) { if (!array[i]) result[1] = i; } return result; } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**