Намерете липсващи елементи от диапазон  


Ниво на трудност Лесно
Често задавани в Делхейвъри GreyOrange LinkedIn Нагаро опера Synopsys
Хашиш Ларсен и Тубро сортиране

Проблемът Намиране на липсващи елементи от диапазон ”заявява, че сте получили масив на различни елементи в рамките на определен диапазон и диапазон, даден като нисък и висок. Намерете всички липсващи елементи в диапазон, който не присъства в масив. Изходът трябва да бъде в сортиран ред.

Пример  

Намерете липсващи елементи от диапазонщифт

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“.

Обяснение

Получаваме декларация за проблем, която иска да открием всички липсващи елементи в масива в даден диапазон като ниски и високи. За да решим това, ще използваме набор и ще съхраняваме стойностите в множеството на дадения масив. Даден ни е диапазон като нисък и висок, ние трябва да отпечатаме всички елементи в рамките на ниски и високи включително.

Вижте също
Последователност на Golomb

За да получим тази поръчка, ние вече съхраняваме елементите на масива в набора. Трябва да изпълним цикъл, инициализиращ 'i' като нисък. изпълняваме цикъла, докато стойността на 'i' стане висока. След това проверете дали комплектът не съдържа стойността „i“, след това отпечатайте „i“. Следователно ще получим всички елементи, които липсват от масив в рамките на даден диапазон. Нека разгледаме един пример.

arr [] = {2, 3, 7, 8} ниско = 1, високо = 9

Трябва да прекосим масива и да поставим всички елементи на масива в набора. Нашият комплект ще стане

комплект = [2,3,7,8]

В цикъл инициализирайте i на ниско и цикълът работи до висок, това означава, че i е равно на low = 1 и high = 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)) където "н" е броят на елементите, присъстващи в масива, "Високо" и „Ниско“ е предоставеният вход.

Вижте също
Дължина на най-големия подмасив със съседни елементи

Сложност на пространството

На), в най-лошия случай, ако всички елементи са различни. Ще трябва да съхраняваме всички елементи. По този начин алгоритъмът изисква линейно време.