k-й відсутній елемент у зростаючій послідовності, якого немає в заданій послідовності


Рівень складності Легко
Часто запитують у Цитадель Expedia Fab Факти IBM SAP Labs
масив Мішанина Пошук

Проблема "k-й відсутній елемент у зростаючій послідовності, якого немає у даній послідовності", говорить про те, що вам дано два масиви. Один з них розміщений у порядку зростання, а інший звичайний невідсортований масив з номером k. Знайдіть k-й відсутній елемент, який відсутній у звичайній послідовності, але присутній у зростаючому масиві послідовності.

Приклад

k-й відсутній елемент у зростаючій послідовності, якого немає в заданій послідовності

[0, 2, 4, 6, 8, 10, 12, 14]
[4, 10, 6, 12, 2 ]
k=2
8

Пояснення

Числа у зростаючій послідовності, яких немає в даному масиві, становлять 0,8,14.

Kth відсутнє число, тобто 2nd число 8

Алгоритм пошуку k-го відсутнього елемента у зростаючій послідовності, якого немає у заданій послідовності

  1. Заявіть a HashSet.
  2. Помістіть усі елементи другого масиву в HashSet.
  3. Установка missingCount в 0.
  4. Під час обходу зростаючого послідовного масиву перевірте:
    1. Якщо набір не містить жодного елемента послідовного масиву
      1. Збільште значення missingCount на 1.
      2. Перевірте, чи значення valueCount дорівнює k.
        • Якщо true, поверніть цей масив [i].
  5. З циклу поверніть -1.

Пояснення

Вам дано два масиви і число k. Один з двох масивів - це зростаюча послідовність, а інший - звичайна невідсортована послідовність. У заяві про проблему сказано, що вам потрібно знайти k-й відсутній елемент у відсортованому масиві послідовностей, якого немає в невідсортованому масиві.

Для цього ми будемо використовувати набір. Ми збираємось пройти другий масив б [] і вставити все його значення в набір. Це тому, що ми можемо перевірити це пізніше і порівняти набір із першим масивом a []. Під час обходу масиву a [], якщо набір не містить цього конкретного значення масиву a [i]. Ми збільшуємо значення missingCount на 1 і одночасно перевірити, чи відсутня кількість стає рівною заданому числу k. Якщо це станеться, ми можемо повернути цей елемент першого масиву.

Давайте розглянемо приклад і зрозуміємо це.

Приклад

масив a [] = [0, 2, 4, 6, 8, 10, 12, 14]

b [] = [4, 10, 6, 12, 2]

k = 2

Відповідно до алгоритму, нам потрібно помістити елементи масиву b [] у набір. Ми зробимо це шляхом обходу масиву b [].

Наш набір стане {4, 10, 6, 12, 2}

Нам потрібно здійснити обхід елементів масиву a [] і перевірити, чи не містить набір елемент arr [i],

i = 0, arr [i] = 0

Набір не містить його, тому збільшиться missingCount = missingCount + 1

missingCount = 1, перевірте, якщо missingCount == k, це хибно.

i = 1, arr [i] = 2

набір містить значення '2', тому він нічого не робить.

i = 2, arr [i] = 4

набір містить значення '4', тому він нічого не робить.

i = 3, arr [i] = 6

набір містить значення '6', тому він нічого не робить.

i = 4, arr [i] = 8

Набір не містить 8, тому збільшиться missingCount = missingCount + 1

missingCount = 2, перевірте, якщо missingCount == k, це правда, тому він поверне arr [i], тобто '8',

Вихід стане 8.

код

Код С ++ для пошуку k-го відсутнього елемента у зростаючій послідовності, якої немає в заданій послідовності

#include <unordered_set>
#include<iostream>

using namespace std;
int find(int A[], int B[], int k, int l1, int l2)
{
  unordered_set<int> myset;
  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  int missingCount = 0;
  for (int i = 0; i < l1; i++) {
    if (myset.find(A[i]) == myset.end())
      missingCount++;
    if (missingCount == k)
      return A[i];
  }

  return -1;
}
int main()
{
    int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
    int b[] = { 4, 10, 6, 12, 2 };

  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);

  int k = 2;
  cout << find(a, b, k, l1, l2);
  return 0;
}
8

Код Java для пошуку k-го відсутнього елемента у зростаючій послідовності, якої немає в заданій послідовності

import java.util.LinkedHashSet;

class kthMissingElement
{
    public static int getMissingElement(int A[], int B[], int k, int l1, int l2)
    {
        LinkedHashSet<Integer> hashset = new LinkedHashSet<>();
        for (int i = 0; i < l2; i++)
            hashset.add(B[i]);

        int missingCount = 0;
        for (int i = 0; i < l1; i++)
        {
            if(!hashset.contains(A[i]) )
                missingCount++;
            if (missingCount == k)
                return A[i];
        }

        return -1;
    }
    public static void main(String[] args)
    {
        int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
        int b[] = { 4, 10, 6, 12, 2 };
        int l1 = a.length;
        int l2 = b.length;

        int k = 2;
        System.out.println(getMissingElement(a, b, k, l1, l2));
    }
}
8

Аналіз складності

Складність часу

O (n1 + n2) де “N1” і “N2” - довжина масиву1 та масиву2. Оскільки ми обвели всі елементи з обох масивів. Складність часу лінійна.

Складність простору

O (n2) де “N2” - довжина масиву2. Оскільки ми зберегли в HashSet лише елементи другого масиву, необхідний простір також є лінійним.