查找范围内缺少的元素


难度级别 易得奖学金
经常问 德里韦里 GreyOrange LinkedIn 长郎 操作 新思
哈希 拉森和图布罗 排序

“查找范围的缺失元素”问题指出您有一个 排列 在特定范围内以及在给定的低和高范围内的不同元素的数量。 查找数组中不存在的范围内的所有缺少的元素。 输出应按排序顺序。

使用案列

查找范围内缺少的元素

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

说明

这些是数组中缺少的数字,范围为低和高,即1和10。

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

说明

这些是数组中缺少的数字,范围为低和高,即1和10。

算法

  1. 声明一个 .
  2. 遍历数组并将所有元素放入集合中。
  3. 当“ i”等于低而“ i”小于等于高时。
    • 如果集合不包含“ i”。
      • 打印“ i”。

说明

我们得到了一个问题陈述,要求找出给定范围内高低之间数组中所有丢失的元素。 为了解决这个问题,我们将使用一个集合并将值存储到给定数组的集合中。 我们给定了一个范围,从高到低,我们必须打印包含在高和低范围内的所有元素。

为了获得该顺序,我们已经将数组元素存储到集合中。 我们需要运行一个循环,将“ i”初始化为低。 我们运行循环直到'i'的值变高。 然后检查集合中是否不包含值“ i”,然后打印“ i”。 因此,我们将获得给定范围内数组中缺少的所有元素。 让我们考虑一个例子。

arr [] = {2,3,7,8}低= 1,高= 9

我们需要遍历数组并将数组的所有元素放入集合中。 我们的集合将变为

set = [2,3,7,8]

在循环中,将i初始化为低,然后循环运行直到高,这意味着'i'等于低= 1和高= 9

i = 1,如果集合中不包含i,则打印1

[1]

i = 2,set的值为'2',并且不执行任何操作。

i = 3,set的值为'3',并且不执行任何操作。

i = 4,如果集合中不包含i,则打印4

[1 4]

i = 5,如果集合中不包含i,则打印5

[1,4,5]

i = 6,如果集合中不包含i,则打印6

[1,4,5,6]

i = 7,set的值为'7',并且不执行任何操作。

i = 8,set的值为'8',并且不执行任何操作。

i = 9,如果集合中不包含i,则打印1

[1、4、5、6、9]

我们的输出将变为:[1、4、5、6、9]

代码

C ++代码查找范围中缺少的元素

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

Java代码查找范围中缺少的元素

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

复杂度分析

时间复杂度

O(n +(高-低+1)) 哪里 “ n” 是数组中存在的元素数, “高” 和 “低的” 是提供的输入。

空间复杂度

上), 在最坏的情况下,如果所有元素都是不同的。 我们必须存储所有元素。 因此使得该算法需要线性时间。