к-ти недостајући елемент у растућој секвенци који није присутан у датој секвенци


Ниво тешкоће Лако
Често питани у Цитадела Екпедиа Фаб Фацтсет ИБМ- САП Лабс
Ред Хасх Претраживање

Проблем „к-ти недостајући елемент у растућој секвенци који није присутан у датој секвенци“ наводи да су вам дата два низа. Један од њих је распоређен у растућем низу, а други нормални несортирани низ са бројем к. Пронађите к-ти недостајући елемент који није присутан у нормалној секвенци, али је присутан у низу редова са све већим редоследом.

Пример

к-ти недостајући елемент у растућој секвенци који није присутан у датој секвенци

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

Објашњење

Бројеви у растућем низу који нису присутни у датом низу су 0,8,14.

Тхе кth недостајући број, тјnd број је 8

Алгоритам за проналажење к-тог недостајућег елемента у растућој секвенци који није присутан у датој секвенци

  1. Изјавите а ХасхСет.
  2. Ставите све елементе другог низа у ХасхСет.
  3. Сет миссингЦоунт да КСНУМКС.
  4. Док обилазите све већи низ секвенци, проверите:
    1. Ако скуп не садржи ниједан елемент секвенцијалног низа
      1. Повећајте вредност миссингЦоунт за 1.
      2. Проверите да ли је вредност миссингЦоунт једнака к.
        • Ако је тачно, вратите тај низ [и].
  5. Из петље вратите -1.

Објашњење

Добијате два низа и број к. Један од два низа је све већа секвенца, а други је нормална неразврстана секвенца. Изјава о проблему каже да морате пронаћи к-ти недостајући елемент у сортираном низу секвенци који није присутан у несортованом низу.

За ово ћемо користити Сет. Прећи ћемо преко другог низа б [] и убаците сву његову вредност у скуп. То је зато што то можемо касније проверити и упоредити скуп са првим низом а []. Док обилази низ а [], ако скуп не садржи ту одређену вредност низа а [и]. Повећавамо вредност миссингЦоунт за 1 и истовремено проверите да ли миссингЦоунт постаје једнак датом броју к. Ако се догоди, можемо вратити тај елемент првог низа.

Размотримо пример и схватимо ово.

Пример

низ а [] = [0, 2, 4, 6, 8, 10, 12, 14]

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

к = 2

Према алгоритму, морамо поставити низ б [] елемената у сет. То ћемо урадити прелазећи низ б [].

Наш сет ће постати {4, 10, 6, 12, 2}

Морамо прећи низ елемената а [] и проверити да ли сет не садржи елемент арр [и],

и = 0, арр [и] = 0

Сет га не садржи, па ће повећати миссингЦоунт = миссингЦоунт + 1

миссингЦоунт = 1, проверите да ли је миссингЦоунт == к, нетачно.

и = 1, арр [и] = 2

сет садржи вредност „2“, тако да не чини ништа.

и = 2, арр [и] = 4

сет садржи вредност „4“, тако да не чини ништа.

и = 3, арр [и] = 6

сет садржи вредност „6“, тако да не чини ништа.

и = 4, арр [и] = 8

Сет не садржи 8, па ће повећати миссингЦоунт = миссингЦоунт + 1

миссингЦоунт = 2, проверите да ли је миссингЦоунт == к, тачно је па ће вратити арр [и] који је '8',

Излаз ће постати 8.

код

Ц ++ код за проналажење к-тог недостајућег елемента у растућој секвенци који није присутан у датој секвенци

#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

Јава код за проналажење к-тог недостајућег елемента у растућој секвенци који није присутан у датој секвенци

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

Анализа сложености

Сложеност времена

О (н1 + н2) где „Н1“  „Н2“ су дужина низа1 и низа2. Пошто смо прешли све елементе из оба низа. Сложеност времена је линеарна.

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

О (н2) где „Н2“ је дужина низа2. Будући да смо у ХасхСет похранили само елементе другог низа, потребан простор је такође линеаран.