跳转至

3731. 找出缺失的元素

来源第 474 场周赛 Q1难度简单分数1217

题目描述

给你一个整数数组 nums ，数组由若干 互不相同 的整数组成。

数组 nums 原本包含了某个范围内的 所有整数 。但现在，其中可能 缺失 部分整数。

该范围内的 最小 整数和 最大 整数仍然存在于 nums 中。

返回一个 有序 列表，包含该范围内缺失的所有整数，并 按从小到大排序。如果没有缺失的整数，返回一个 空 列表。

 

示例 1：

输入： nums = [1,4,2,5]

输出： [3]

解释：

最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。其中只有 3 缺失。

示例 2：

输入： nums = [7,8,6,9]

输出： []

解释：

最小整数为 6，最大整数为 9，因此完整的范围为 [6,7,8,9]。所有整数均已存在，因此没有缺失的整数。

示例 3：

输入： nums = [5,1]

输出： [2,3,4]

解释：

最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。缺失的整数为 2、3 和 4。

 

提示：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 100

解法

方法一：哈希表

思考

范围由数组最小、最大值确定，缺失值即该闭区间中未出现者。\(n\le 100\)，放入集合后扫描 \((\textit{mn},\textit{mx})\) 即可按升序列出。

我们先找出数组 \(\textit{nums}\) 中的最小值和最大值，记为 \(\textit{mn}\) 和 \(\textit{mx}\)。然后我们使用哈希表存储数组 \(\textit{nums}\) 中的所有元素。

接下来，我们遍历区间 \([\textit{mn} + 1, \textit{mx} - 1]\)，对于每个整数 \(x\)，如果 \(x\) 不在哈希表中，我们就将其加入答案列表中。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

1
2
3
4
5
class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        mn, mx = min(nums), max(nums)
        s = set(nums)
        return [x for x in range(mn + 1, mx) if x not in s]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> findMissingElements(int[] nums) {
        int mn = 100, mx = 0;
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            mn = Math.min(mn, x);
            mx = Math.max(mx, x);
            s.add(x);
        }
        List<Integer> ans = new ArrayList<>();
        for (int x = mn + 1; x < mx; ++x) {
            if (!s.contains(x)) {
                ans.add(x);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int mn = 100, mx = 0;
        unordered_set<int> s;
        for (int x : nums) {
            mn = min(mn, x);
            mx = max(mx, x);
            s.insert(x);
        }
        vector<int> ans;
        for (int x = mn + 1; x < mx; ++x) {
            if (!s.count(x)) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func findMissingElements(nums []int) (ans []int) {
    mn, mx := 100, 0
    s := make(map[int]bool)
    for _, x := range nums {
        mn = min(mn, x)
        mx = max(mx, x)
        s[x] = true
    }
    for x := mn + 1; x < mx; x++ {
        if !s[x] {
            ans = append(ans, x)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function findMissingElements(nums: number[]): number[] {
    let [mn, mx] = [100, 0];
    const s = new Set<number>();
    for (const x of nums) {
        mn = Math.min(mn, x);
        mx = Math.max(mx, x);
        s.add(x);
    }
    const ans: number[] = [];
    for (let x = mn + 1; x < mx; ++x) {
        if (!s.has(x)) {
            ans.push(x);
        }
    }
    return ans;
}

评论