645. 错误的集合

Posted on | In
Words count in article: 351 | Reading time ≈ 1

题目

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

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

示例1：

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

示例2：

1
2
输入：nums = [1,1]
输出：[1,2]

提示：

  1. 2 <= nums.length <= 10^4
  2. 1 <= nums[i] <= 10^4

解法

解法一：

使用一个中间数组来保存出现过的数字。即，将中间数组对应索引为该数字的值置为1，如果一个数字，去值位的时候发现该位置上已经是1了， 则说明该数字是多出来的数字。最后扫描一遍中间数组，未置0的则为缺失的数字。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] findErrorNums(int[] nums) {
        int more = -1;
        int less = -1;
        int[] result = new int[nums.length + 1];
        for (int i = 0; i < nums.length;i++) {
        	if (result[nums[i]] == 1) {
        		more = nums[i];
        	} else {
				result[nums[i]] = 1;
			}
        }
        
        for (int i = 1;i < result.length;i++) {
        	if(result[i] == 0) {
        		less = i;
        		break;
        	}
        }
        return new int[] {more, less};
    }
}
0%