k-й отсутствующий элемент в возрастающей последовательности, которого нет в данной последовательности


Сложный уровень Легко
Часто спрашивают в Цитадель Expedia Потрясающий Набор фактов IBM SAP Labs
массив Hash Поиск

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

Пример

k-й отсутствующий элемент в возрастающей последовательности, которого нет в данной последовательности

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

объяснение

Числа в возрастающей последовательности, которых нет в данном массиве, равны 0,8,14.

Кth отсутствующее число, например, 2nd номер 8

Алгоритм поиска k-го отсутствующего элемента в возрастающей последовательности, которого нет в данной последовательности

  1. Объявить HashSet.
  2. Поместите все элементы второго массива в HashSet.
  3. Набор missingCount в 0.
  4. Просматривая увеличивающийся последовательный массив, проверьте:
    1. Если набор не содержит ни одного последовательного элемента массива
      1. Увеличьте значение missingCount на 1.
      2. Проверьте, равно ли значение missingCount k.
        • Если это правда, вернуть этот массив [i].
  5. Выйдя из цикла, верните -1.

объяснение

Вам даны два массива и число k. Один из двух массивов - это возрастающая последовательность, а другой - обычная несортированная последовательность. В формулировке задачи говорится, что вам нужно найти k-й отсутствующий элемент в отсортированном массиве последовательностей, которого нет в несортированном массиве.

Мы собираемся использовать для этого Set. Мы собираемся пройти по второму массиву b [] и вставляем все его значение в набор. Это потому, что мы можем проверить это позже и сравнить набор с первым массивом а []. При обходе массива a [], если набор не содержит этого конкретного значения массива a [i]. Мы увеличиваем стоимость missingCount на 1 и одновременно проверяем, становится ли значение missingCount равным заданному числу k. Если это так, мы можем вернуть этот элемент первого массива.

Давайте рассмотрим пример и поймем это.

Пример

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

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

к = 2

Согласно алгоритму, нам нужно поместить элементы массива b [] в набор. Мы сделаем это путем обхода массива b [].

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

Нам нужно пройти по массиву a [] elements и проверить, не содержит ли set элемент arr [i],

i = 0, arr [i] = 0

Набор не содержит его, поэтому он будет увеличиваться missingCount = missingCount + 1

missingCount = 1, проверить, если missingCount == k, это ложь.

i = 1, arr [i] = 2

set содержит это значение «2», поэтому ничего не делает.

i = 2, arr [i] = 4

set содержит это значение «4», поэтому ничего не делает.

i = 3, arr [i] = 6

set содержит это значение «6», поэтому ничего не делает.

i = 4, arr [i] = 8

Набор не содержит 8, поэтому он будет увеличиваться missingCount = missingCount + 1

missingCount = 2, проверьте, является ли missingCount == k истинным, поэтому он вернет arr [i], который равен '8',

На выходе будет 8.

Код:

Код C ++ для поиска 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

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

Сложность времени

О (п1 + п2) в котором «N1» и «N2» - это длина массивов array1 и array2. Поскольку мы прошли все элементы из обоих массивов. Временная сложность линейна.

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

O (n2) в котором «N2» - длина array2. Поскольку мы сохранили только элементы второго массива в HashSet, необходимое пространство также является линейным.