給定序列中不存在的第k個缺失元素(按遞增順序)  


難度級別 容易獎學金
經常問 堡壘 Expedia的 事實集 IBM SAP實驗室
排列 哈希 搜索

問題“在給定序列中不存在的第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. 聲明一個 哈希集.
  2. 將第二個數組的所有元素放入HashSet中。
  3. 在你的生活中 失踪人數 到0。
  4. 遍歷遞增的順序數組時,請檢查:
    1. 如果集合不包含任何順序數組元素
      1. 將missingCount值增加1。
      2. 檢查missingCount值是否等於k。
        • 如果為true,則返回該數組[i]。
  5. 跳出循環,返回-1。

解釋

給出兩個數組和一個數字k。 這兩個數組之一是遞增序列,另一個是正常的未排序序列。 問題陳述指出,您必須在未排序數組中不存在的已排序序列數組中找到第k個缺少的元素。

也可以看看
在數組中找到最大的d,使a + b + c = d

我們將為此使用Set。 我們將遍歷第二個數組 b [] 並將其所有值插入集合。 這是因為我們可以稍後對其進行檢查,並將其與第一個數組進行比較 一種[]。 在遍歷數組a []時,如果集合不包含數組a [i]的特定值。 我們增加價值 失踪人數 用1並同時檢查missingCount是否等於給定數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 []元素,並檢查set是否不包含arr [i]元素,

i = 0,arr [i] = 0

集合不包含它,因此它將增加missingCount = missingCount + 1

missingCount = 1,請檢查missingCount == k是否為false。

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

複雜度分析  

時間複雜度

O(n1 + n2) 哪裡 “ n1” 及 “ n2” 是array1和array2的長度。 由於我們遍歷了兩個數組中的所有元素。 時間複雜度是線性的。

空間複雜度

O(n2) 哪裡 “ n2” 是array2的長度。 因為我們僅將第二個數組的元素存儲到HashSet中,所以所需的空間也是線性的。