| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
简单 |
|
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1：
输入：nums = [1,2,2,4] 输出：[2,3]
示例 2：
输入：nums = [1,1] 输出：[1,2]
提示：
2 <= nums.length <= 1041 <= nums[i] <= 104
我们用
那么
时间复杂度
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
n = len(nums)
s1 = (1 + n) * n // 2
s2 = sum(set(nums))
s = sum(nums)
return [s - s2, s1 - s2]class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int s1 = (1 + n) * n / 2;
int s2 = 0;
Set<Integer> set = new HashSet<>();
int s = 0;
for (int x : nums) {
if (set.add(x)) {
s2 += x;
}
s += x;
}
return new int[] {s - s2, s1 - s2};
}
}class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int s1 = (1 + n) * n / 2;
int s2 = 0;
unordered_set<int> set(nums.begin(), nums.end());
for (int x : set) {
s2 += x;
}
int s = accumulate(nums.begin(), nums.end(), 0);
return {s - s2, s1 - s2};
}
};func findErrorNums(nums []int) []int {
n := len(nums)
s1 := (1 + n) * n / 2
s2, s := 0, 0
set := map[int]bool{}
for _, x := range nums {
if !set[x] {
set[x] = true
s2 += x
}
s += x
}
return []int{s - s2, s1 - s2}
}function findErrorNums(nums: number[]): number[] {
const n = nums.length;
const s1 = (n * (n + 1)) >> 1;
const s2 = [...new Set(nums)].reduce((a, b) => a + b);
const s = nums.reduce((a, b) => a + b);
return [s - s2, s1 - s2];
}use std::collections::HashSet;
impl Solution {
pub fn find_error_nums(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len() as i32;
let s1 = ((1 + n) * n) / 2;
let s2 = nums
.iter()
.cloned()
.collect::<HashSet<i32>>()
.iter()
.sum::<i32>();
let s: i32 = nums.iter().sum();
vec![s - s2, s1 - s2]
}
}我们也可以一种更加直观的方法，直接用哈希表
接下来遍历
时间复杂度
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
cnt = Counter(nums)
n = len(nums)
ans = [0] * 2
for x in range(1, n + 1):
if cnt[x] == 2:
ans[0] = x
if cnt[x] == 0:
ans[1] = x
return ansclass Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
Map<Integer, Integer> cnt = new HashMap<>(n);
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
}
int[] ans = new int[2];
for (int x = 1; x <= n; ++x) {
int t = cnt.getOrDefault(x, 0);
if (t == 2) {
ans[0] = x;
} else if (t == 0) {
ans[1] = x;
}
}
return ans;
}
}class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> cnt;
for (int x : nums) {
++cnt[x];
}
vector<int> ans(2);
for (int x = 1; x <= n; ++x) {
if (cnt[x] == 2) {
ans[0] = x;
} else if (cnt[x] == 0) {
ans[1] = x;
}
}
return ans;
}
};func findErrorNums(nums []int) []int {
n := len(nums)
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
ans := make([]int, 2)
for x := 1; x <= n; x++ {
if cnt[x] == 2 {
ans[0] = x
} else if cnt[x] == 0 {
ans[1] = x
}
}
return ans
}function findErrorNums(nums: number[]): number[] {
const n = nums.length;
const cnt: Map<number, number> = new Map();
for (const x of nums) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
const ans: number[] = new Array(2).fill(0);
for (let x = 1; x <= n; ++x) {
const t = cnt.get(x) || 0;
if (t === 2) {
ans[0] = x;
} else if (t === 0) {
ans[1] = x;
}
}
return ans;
}impl Solution {
pub fn find_error_nums(nums: Vec<i32>) -> Vec<i32> {
let mut xs = 0;
for (i, x) in nums.iter().enumerate() {
xs ^= ((i + 1) as i32) ^ x;
}
let mut a = 0;
let lb = xs & -xs;
for (i, x) in nums.iter().enumerate() {
if (((i + 1) as i32) & lb) != 0 {
a ^= (i + 1) as i32;
}
if (*x & lb) != 0 {
a ^= *x;
}
}
let b = xs ^ a;
for x in nums.iter() {
if *x == a {
return vec![a, b];
}
}
vec![b, a]
}
}根据异或运算的性质，对于整数
由于这两个数字不相等，因此异或结果中至少存在一位为
接下来我们只需要判断
时间复杂度
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
xs = 0
for i, x in enumerate(nums, 1):
xs ^= i ^ x
a = 0
lb = xs & -xs
for i, x in enumerate(nums, 1):
if i & lb:
a ^= i
if x & lb:
a ^= x
b = xs ^ a
for x in nums:
if x == a:
return [a, b]
return [b, a]class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int xs = 0;
for (int i = 1; i <= n; ++i) {
xs ^= i ^ nums[i - 1];
}
int lb = xs & -xs;
int a = 0;
for (int i = 1; i <= n; ++i) {
if ((i & lb) > 0) {
a ^= i;
}
if ((nums[i - 1] & lb) > 0) {
a ^= nums[i - 1];
}
}
int b = xs ^ a;
for (int i = 0; i < n; ++i) {
if (nums[i] == a) {
return new int[] {a, b};
}
}
return new int[] {b, a};
}
}class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int xs = 0;
for (int i = 1; i <= n; ++i) {
xs ^= i ^ nums[i - 1];
}
int lb = xs & -xs;
int a = 0;
for (int i = 1; i <= n; ++i) {
if (i & lb) {
a ^= i;
}
if (nums[i - 1] & lb) {
a ^= nums[i - 1];
}
}
int b = xs ^ a;
for (int i = 0; i < n; ++i) {
if (nums[i] == a) {
return {a, b};
}
}
return {b, a};
}
};func findErrorNums(nums []int) []int {
xs := 0
for i, x := range nums {
xs ^= x ^ (i + 1)
}
lb := xs & -xs
a := 0
for i, x := range nums {
if (i+1)&lb != 0 {
a ^= (i + 1)
}
if x&lb != 0 {
a ^= x
}
}
b := xs ^ a
for _, x := range nums {
if x == a {
return []int{a, b}
}
}
return []int{b, a}
}function findErrorNums(nums: number[]): number[] {
const n = nums.length;
let xs = 0;
for (let i = 1; i <= n; ++i) {
xs ^= i ^ nums[i - 1];
}
const lb = xs & -xs;
let a = 0;
for (let i = 1; i <= n; ++i) {
if (i & lb) {
a ^= i;
}
if (nums[i - 1] & lb) {
a ^= nums[i - 1];
}
}
const b = xs ^ a;
return nums.includes(a) ? [a, b] : [b, a];
}