LeetCode第645题错误的集合

题目来源

题目描述

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

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

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

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

解题思路

第一种解法

一个数组包含1到n的整数，第一步调整数组中的数字位置，比如数字1放在数组中1的位置

代码1

class Solution { public int[] findErrorNums(int[] nums) { for (int i = 0; i < nums.length; i++) { while (nums[i] != i + 1 && 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; } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }

第二种解法

1、求解出1到n的整数的总和long sum = (n*(n + 1)) / 2 2、遍历整个数组，用HashSet来装每个数字，如果set.contains(i)，则i为重复出现的数字

class Solution { public int[] findErrorNums(int[] nums) { Set<Integer> set = new HashSet<>(); int duplicate = 0, n = nums.length; long sum = (n*(n + 1)) / 2; for(int i : nums){ if(set.contains(i)) duplicate = i; sum -= i; set.add(i); } return new int[]{duplicate, duplicate + (int)sum}; } }