範囲の欠落している要素を見つける


難易度 簡単に
よく聞かれる デリーベリー GreyOrange LinkedIn ナガロ Opera シノプシス
ハッシュ ラーセンとトゥーブロ 並べ替え(ソート)

「範囲の欠落している要素を見つける」という問題は、 配列 特定の範囲内の個別の要素と、低および高として指定された範囲の。 配列に存在しない範囲内の欠落しているすべての要素を検索します。 出力はソートされた順序である必要があります。

範囲の欠落している要素を見つける

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

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

説明

これらは、lowとhigh、つまり1と10として指定された範囲内の配列で欠落している数値です。

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

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

説明

これらは、lowとhigh、つまり1と10として指定された範囲内の配列で欠落している数値です。

アルゴリズム

  1. 宣言する セッションに.
  2. 配列をトラバースし、すべての要素をセットに入れます。
  3. 「i」は低に等しく、「i」は高に等しくありません。
    • セットに「i」が含まれていない場合。
      • 'i'を印刷します。

説明

与えられた範囲内の配列内の欠落しているすべての要素を低および高として見つけるように求める問題ステートメントが与えられます。 これを解決するために、セットを使用して、指定された配列のセットに値を格納します。 低と高の範囲が与えられているので、すべての要素を低と高の範囲内で印刷する必要があります。

その順序を取得するために、配列要素をセットにすでに格納しています。 'i'をlowに初期化するループを実行する必要があります。 'i'の値が高くなるまでループを実行します。 次に、セットに値「i」が含まれていないかどうかを確認してから、「i」を出力します。 したがって、指定された範囲内の配列から欠落しているすべての要素を取得します。 例を考えてみましょう。

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

配列を走査し、配列のすべての要素をセットに入れる必要があります。 私たちのセットは

set = [2,3,7,8]

ループでは、iをlowに初期化し、ループはhighまで実行されます。これは、「i」がlow = 1およびhigh = 9に等しいことを意味します。

i = 1、セットにiが含まれていない場合、1を出力します

[1]

i = 2、セットの値は「2」で、何もしません。

i = 3、セットの値は「3」で、何もしません。

i = 4、セットにiが含まれていない場合、4を出力します

[1、4]

i = 5、セットにiが含まれていない場合、5を出力します

[1、4、5]

i = 6、セットにiが含まれていない場合、6を出力します

[1、4、5、6]

i = 7、セットの値は「7」で、何もしません。

i = 8、セットの値は「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)) where 「n」 配列に存在する要素の数です。 "高い"  「低い」 提供される入力です。

スペースの複雑さ

オン)、 最悪の場合、すべての要素が異なる場合。 すべての要素を保存する必要があります。 したがって、アルゴリズムを作成するには線形時間が必要です。