Найти недостающие элементы диапазона


Сложный уровень Легко
Часто спрашивают в Деливери СерыйОранжевый LinkedIn Нагарро Opera Synopsys
Hash Ларсен и Тубро Сортировка

Проблема «Найти недостающие элементы диапазона» гласит, что вам дается массив различных элементов в пределах определенного диапазона и диапазона, заданного как низкий и высокий. Найдите все недостающие элементы в диапазоне, которого нет в массиве. Вывод должен быть отсортирован.

Пример

Найти недостающие элементы диапазона

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' равно 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)) в котором «Н» количество элементов в массиве, «Высокий» и "низкий" предоставлен вход.

Космическая сложность

На), в худшем случае, если все элементы различны. Придется хранить все элементы. Таким образом, алгоритм требует линейного времени.