手机网站模板下载免费,网站开发思维导图内容,wordpress 前端 插件,服装公司网站首页集合 s 包含从 1 到 n 的整数。不幸的是#xff0c;因为数据错误#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值#xff0c;导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出…集合 s 包含从 1 到 n 的整数。不幸的是因为数据错误导致集合里面某一个数字复制了成了集合里面的另外一个数字的值导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数再找到丢失的整数将它们以数组的形式返回。 我想的太简单了 class Solution {public int[] findErrorNums(int[] nums) {Arrays.sort(nums);for(int i 0;i nums.length-1;i){if(nums[i] nums[i1]){nums[i1] nums[i] 1;}}return nums;}
} 官解 方法一排序 将数组排序之后比较每对相邻的元素即可找到错误的集合。 寻找重复的数字较为简单如果相邻的两个元素相等则该元素为重复的数字。 寻找丢失的数字相对复杂可能有以下两种情况 如果丢失的数字大于 1 且小于 n则一定存在相邻的两个元素的差等于 2这两个元素之间的值即为丢失的数字 如果丢失的数字是 1 或 n则需要另外判断。 为了寻找丢失的数字需要在遍历已排序数组的同时记录上一个元素然后计算当前元素与上一个元素的差。考虑到丢失的数字可能是 1因此需要将上一个元素初始化为 0。 当丢失的数字小于 n 时通过计算当前元素与上一个元素的差即可得到丢失的数字 如果 nums[n−1]≠n则丢失的数字是 n。 class Solution {public int[] findErrorNums(int[] nums) {int[] errorNums new int[2];int n nums.length;Arrays.sort(nums);int prev 0;for (int i 0; i n; i) {int curr nums[i];if (curr prev) {errorNums[0] prev;} else if (curr - prev 1) {errorNums[1] prev 1;}prev curr;}if (nums[n - 1] ! n) {errorNums[1] n;}return errorNums;}
} 方法二哈希表 重复的数字在数组中出现 2 次丢失的数字在数组中出现 0 次其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中出现的次数然后遍历从 1 到 n 的每个数字分别找到出现 2 次和出现 0 次的数字即为重复的数字和丢失的数字。 class Solution {public int[] findErrorNums(int[] nums) {int[] errorNums new int[2];int n nums.length;MapInteger, Integer map new HashMapInteger, Integer();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}for (int i 1; i n; i) {int count map.getOrDefault(i, 0);if (count 2) {errorNums[0] i;} else if (count 0) {errorNums[1] i;}}return errorNums;}
}
