Мужийн алга болсон элементүүдийг олох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Дели Саарал улбар шар LinkedIn Нагарро Opera Синопсис
Хаш Ларсен ба Тубро Ангилах

Асуудал нь мужийн алга болсон элементүүдийг олох "гэсэн үг танд өгөгдсөн болно массив тодорхой муж доторх ялгаатай элементүүд ба бага ба өндөр гэж өгсөн муж. Массивт байхгүй бүх алга болсон элементүүдийг хайж олох. Гаралт нь эрэмбэлэгдсэн дарааллаар байх ёстой.

Жишээ нь

Мужийн алга болсон элементүүдийг олох

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. Мэдүүлэх a багц.
  2. Массивыг дайрч, бүх элементүүдийг багцад оруулна.
  3. “I” нь бага, “i” нь ихтэй тэнцэхгүй байхад.
    • Хэрэв багц нь "i" агуулаагүй бол.
      • 'I' хэвлэх.

Тайлбар

Бид өгөгдсөн муж доторх массивын бүх алга болсон элементүүдийг бага, өндөр гэж олохыг хүссэн асуудлын хариуг өгсөн болно. Үүнийг шийдэхийн тулд бид багцыг ашиглаж, өгөгдсөн массивын олонлог дотор утгыг хадгалах болно. Бидэнд бага ба өндөр гэсэн муж өгөгдсөн тул бүх элементүүдийг бага, өндөр багтаамжтай хэвлэх ёстой.

Энэ захиалгыг авахын тулд бид массивын элементүүдийг багцад аль хэдийн хадгалдаг. Бид "i" -г бага гэж эхлүүлэх давталтыг ажиллуулах хэрэгтэй. бид 'i' утга өндөр болох хүртэл давталтыг ажиллуулна. Дараа нь багц нь 'i' утгыг агуулаагүй эсэхийг шалгаад дараа нь 'i' -г хэвлэ. Тиймээс бид өгөгдсөн хүрээнд массиваас дутуу байгаа бүх элементүүдийг авах болно. Нэг жишээг авч үзье.

arr [] = {2, 3, 7, 8} бага = 1, өндөр = 9

Бид массивыг дайрч, массивын бүх элементүүдийг олонлогт оруулах хэрэгтэй. Бидний багц болно

багц = [2,3,7,8]

Гогцоонд i-г эхлүүлж, гогцоо нь өндөр болтол ажиллана, энэ нь 'i' нь доогуур = 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), хамгийн муу тохиолдолд бүх элементүүд нь ялгаатай байвал. Бид бүх элементүүдийг хадгалах хэрэгтэй болно. Тиймээс алгоритм хийхэд шугаман цаг хугацаа шаардагдана.