2020-10-05

力扣刷题

统计数组中的元素

645.错误的集合

集合 S 包含从1到 n的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1: java 输入: nums = [1,2,2,4] 输出: [2,3]

注意:

给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/set-mismatch 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一次提交

class Solution { public int[] findErrorNums(int[] nums) { Arrays.sort(nums); int[] a = new int[2]; for(int i=0;i<nums.length;i++){ int b = nums[0]; if(nums[i]!=i+b){ a[0]=nums[i]; a[1]=i+1; } } return a; } }

思路1：先排序，后查找 重点：怎么找到缺失数据。 重新审题，数组是从1开始的直到n，考虑结尾缺失以及开头缺失 缺失数据特点：和周围数据差一 修改后：

public class Solution { public int[] findErrorNums(int[] nums) { Arrays.sort(nums); int dup = -1, miss = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) dup = nums[i]; else if (nums[i] > nums[i - 1] + 1) miss = nums[i - 1] + 1; } miss = nums[nums.length - 1] != nums.length ? nums.length : miss; return new int[] {dup, miss}; } }