Диапазондун жок элементтерин табуу


Кыйынчылык деңгээли жеңил
Көп суралган Delhivery GreyOrange LinkedIn Нагарро опера Synopsys
таштанды Ларсен & Toubro сорттоо

Маселе, диапазондун жоголгон элементтерин табуу ”деген аталыш менен берилген согуштук тизме белгилүү бир диапазондогу жана төмөнкү жана жогорку деп берилген ар башка элементтердин. Массивде жок болгон бардык жетишпеген элементтерди табыңыз. Чыгуу иреттелген тартипте болушу керек.

мисал

Диапазондун жок элементтерин табуу

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.

Algorithm

  1. Декларация a коюлган.
  2. Массивди кыдырып, бардык элементтерди жыйындыга салыңыз.
  3. Ал эми "i" төмөнкүгө барабар, ал эми "i" чоңго барабар.
    • Эгерде топтомдо "i" жок болсо.
      • 'I' басып чыгаруу.

түшүндүрүү

Бизге массивдеги бардык жетишпеген элементтерди берилген диапазондогу төмөн жана жогору деп табууну сураган көйгөйдү билдирүү берилген. Муну чечүү үчүн биз топтомду колдонобуз жана берилген массивдин жыйындысына баалуулуктарды сактайбыз. Бизге төмөн жана жогорку диапазон берилет, бардык элементтерди төмөнкү жана жогорку деңгээлде басып чыгаруу керек.

Мындай буйрукту алуу үчүн биз массивдин элементтерин көптүк кылып сактайбыз. Биз "i" инициализациясын баштапкы циклди иштетишибиз керек. биз циклди 'i' мааниси жогору болгонго чейин иштетебиз. Андан кийин топтомдо 'i' мааниси жок экендигин текшерип, андан кийин 'i' басып чыгарыңыз. Демек, биз массивден жок болгон бардык элементтерди берилген аралыкта алабыз. Келгиле, бир мисал карап көрөлү.

arr [] = {2, 3, 7, 8} төмөн = 1, жогорку = 9

Биз массивди аралап өтүп, массивдин бардык элементтерин жыйындыга киргизишибиз керек. Биздин топтом болуп калат

set = [2,3,7,8]

Циклде и -ди баштап, цикл жогорку деңгээлге чейин иштейт, бул "мен" төмөн = 1ге жана жогорку = 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)) кайда "N" массивдеги элементтердин саны, "Бийик" жана "Төмөн" берилген киргизүү болуп саналат.

Космостун татаалдыгы

O (n), эң начар учурда, эгерде бардык элементтер айырмаланса. Бардык элементтерди сактоого туура келет. Ошентип, алгоритмди түзүү сызыктуу убакытты талап кылат.