645. Set Mismatch

leetcode easy

#array#csharp#easy#hash-table#leetcode#search

Task

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

Input: nums = [1,2,2,4]

Output: [2,3]

C# solution

matched/original

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        int n = nums.Length;
        HashSet<int> numSet = new HashSet<int>();
        int duplicate = -1;
        foreach (int num in nums) {
            if (!numSet.Add(num)) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - numSet.Sum();
        return new int[] { duplicate, missing };
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& FindErrorNums(vector<int>& nums) {
        int n = nums.size();
        HashSet<int> numSet = new HashSet<int>();
        int duplicate = -1;
        foreach (int num in nums) {
            if (!numSet.push_back(num)) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - numSet.Sum();
        return new int[] { duplicate, missing };
    }
}

Java solution

matched/original

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        Set<Integer> numSet = new HashSet<>();
        int duplicate = -1;
        for (int num : nums) {
            if (!numSet.add(num)) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - numSet.stream().mapToInt(Integer::intValue).sum();
        return new int[]{duplicate, missing};
    }
}

JavaScript solution

matched/original

var findErrorNums = function(nums) {
    let numSet = new Set();
    let duplicate = -1;
    const n = nums.length;
    for (let num of nums) {
        if (numSet.has(num)) {
            duplicate = num;
        }
        numSet.add(num);
    }
    let missing = (n * (n + 1)) / 2 - [...numSet].reduce((a, b) => a + b, 0);
    return [duplicate, missing];
};

Python solution

matched/original

def findErrorNums(nums):
    n = len(nums)
    num_set = set()
    duplicate = -1
    for num in nums:
        if num in num_set:
            duplicate = num
        num_set.add(num)
    missing = (n * (n + 1)) // 2 - sum(num_set)
    return [duplicate, missing]

Go solution

matched/original

func findErrorNums(nums []int) []int {
    numSet := make(map[int]bool)
    duplicate := -1
    n := len(nums)
    for _, num := range nums {
        if numSet[num] {
            duplicate = num
        }
        numSet[num] = true
    }
    sum := 0
    for num := range numSet {
        sum += num
    }
    missing := (n * (n + 1)) / 2 - sum
    return []int{duplicate, missing}
}

Explanation

Algorithm

Пройдите по массиву, используя набор для отслеживания чисел, чтобы определить дублированное число.

Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

Верните дублированное и отсутствующее числа в виде массива.

😎