在给定序列中不存在的递增序列中的第k个缺失元素-yiteyi-C++库

给定两个序列，一个是递增序列 a[] 另一个是正常序列 b[] ，在递增序列中找到给定序列中不存在的第K个缺失元素。如果没有第k个缺失元素，则输出-1 例如：

null

Input:  a[] = {0, 2, 4, 6, 8, 10, 12, 14, 15};        b[] = {4, 10, 6, 8, 12};          k = 3Output: 14Explanation : The numbers from increasing sequence thatare not present in the given sequence are 0, 2, 14, 15.The 3rd missing number is 14.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

n1 递增序列a[]上的元素数。 n2 给定序列b[]中的元素数。 A. 幼稚的方法 就是对递增序列中的每个元素进行迭代，检查它是否存在于给定序列中，并保留一个不存在元素的计数器，并打印第k个不存在元素。这是不够有效的，因为它有两个嵌套的for循环，需要O（n2）。时间复杂度：O（n1*n2）辅助空间：O（1）一 有效的方法 就是使用散列 .我们将给定序列的所有元素存储在哈希表中。然后我们遍历递增序列的所有元素。对于每个元素，我们在哈希表中搜索它。若元素存在于not哈希表中，那个么我们增加缺失元素的计数。如果count变为k，则返回缺少的元素。下面是上述方法的实现

C++

                         // C++ program to find the k-th missing element                       
                         // in a given sequence                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns k-th missing element. It returns -1 if                       
                         // no k is more than number of missing elements.                       
                         int                                     find(                                     int                                     a[],                                     int                                     b[],                                     int                                     k,                                     int                                     n1,                                     int                                     n2)                       
                         {                       
                                                 // Insert all elements of givens sequence b[].                       
                                                 unordered_set<                                     int                                     > s;                       
                                                 for                                     (                                     int                                     i = 0; i < n2; i++)                       
                                                 s.insert(b[i]);                       
           
                                                 // Traverse through increasing sequence and                       
                                                 // keep track of count of missing numbers.                       
                                                 int                                     missing = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n1; i++) {                       
                                                 if                                     (s.find(a[i]) == s.end())                       
                                                 missing++;                       
                                                 if                                     (missing == k)                       
                                                 return                                     a[i];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         // driver program to test the above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 0, 2, 4, 6, 8, 10, 12, 14, 15 };                       
                                                 int                                     b[] = { 4, 10, 6, 8, 12 };                       
                                                 int                                     n1 =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 int                                     n2 =                                     sizeof                                     (b) /                                     sizeof                                     (b[0]);                       
           
                                                 int                                     k = 3;                       
                                                 cout << find(a, b, k, n1, n2);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the k-th missing element                       
                         // in a given sequence                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Returns k-th missing element. It returns -1 if                       
                         // no k is more than number of missing elements.                       
                         static                                     int                                     find(                                     int                                     a[],                                     int                                     b[],                                     int                                     k,                                     int                                     n1,                                     int                                     n2)                       
                         {                       
                                                 // Insert all elements of givens sequence b[].                       
                                                 LinkedHashSet<Integer> s =                                     new                                     LinkedHashSet<>();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n2; i++)                       
                                                 s.add(b[i]);                       
           
                                                 // Traverse through increasing sequence and                       
                                                 // keep track of count of missing numbers.                       
                                                 int                                     missing =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n1; i++)                       
                                                 {                       
                                                 if                                     (!s.contains(a[i]) )                       
                                                 missing++;                       
                                                 if                                     (missing == k)                       
                                                 return                                     a[i];                       
                                                 }                       
           
                                                 return                                     -                                     1                                     ;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     a[] = {                                     0                                     ,                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     8                                     ,                                     10                                     ,                                     12                                     ,                                     14                                     ,                                     15                                     };                       
                                                 int                                     b[] = {                                     4                                     ,                                     10                                     ,                                     6                                     ,                                     8                                     ,                                     12                                     };                       
                                                 int                                     n1 = a.length;                       
                                                 int                                     n2 = b.length;                       
           
                                                 int                                     k =                                     3                                     ;                       
                                                 System.out.println(find(a, b, k, n1, n2));                       
                         }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       

Python3

                         # Python3 program to find the k-th                       
                         # missing element in a given sequence                       
           
           
                         # Returns k-th missing element. It returns -1 if                       
                         # no k is more than number of missing elements.                       
                         def                                     find(a, b, k, n1, n2):                       
           
                                                 # insert all elements of                       
                                                 # given sequence b[].                       
                                                 s                                     =                                     set                                     ()                       
                                   
                                                 for                                     i                                     in                                     range                                     (n2):                       
                                                 s.add(b[i])                       
           
                                                 # Traverse through increasing sequence and                       
                                                 # keep track of count of missing numbers.                       
                                                 missing                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n1):                       
                                                 if                                     a[i]                                     not                                     in                                     s:                       
                                                 missing                                     +                                     =                                     1                       
                                                 if                                     missing                                     =                                     =                                     k:                       
                                                 return                                     a[i]                       
                                                 return                                     -                                     1                       
           
                         # Driver code                       
                         a                                     =                                     [                                     0                                     ,                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     8                                     ,                                     10                                     ,                                     12                                     ,                                     14                                     ,                                     15                                     ]                       
                         b                                     =                                     [                                     4                                     ,                                     10                                     ,                                     6                                     ,                                     8                                     ,                                     12                                     ]                       
                         n1                                     =                                     len                                     (a)                       
                         n2                                     =                                     len                                     (b)                       
                         k                                     =                                     3                       
                         print                                     (find(a, b, k, n1, n2))                       
           
                         # This code is contributed by Shrikant13                       

C#

                         // C# program to find the k-th missing element                       
                         // in a given sequence                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Returns k-th missing element. It returns -1 if                       
                         // no k is more than number of missing elements.                       
                         static                                     int                                     find(                                     int                                     []a,                                     int                                     []b,                                     int                                     k,                                     int                                     n1,                                     int                                     n2)                       
                         {                       
                                                 // Insert all elements of givens sequence b[].                       
                                                 HashSet<                                     int                                     > s =                                     new                                     HashSet<                                     int                                     >();                       
                                                 for                                     (                                     int                                     i = 0; i < n2; i++)                       
                                                 s.Add(b[i]);                       
           
                                                 // Traverse through increasing sequence and                       
                                                 // keep track of count of missing numbers.                       
                                                 int                                     missing = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n1; i++)                       
                                                 {                       
                                                 if                                     (!s.Contains(a[i]) )                       
                                                 missing++;                       
                                                 if                                     (missing == k)                       
                                                 return                                     a[i];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     []a = { 0, 2, 4, 6, 8, 10, 12, 14, 15 };                       
                                                 int                                     []b = { 4, 10, 6, 8, 12 };                       
                                                 int                                     n1 = a.Length;                       
                                                 int                                     n2 = b.Length;                       
           
                                                 int                                     k = 3;                       
                                                 Console.WriteLine(find(a, b, k, n1, n2));                       
                         }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Javascript

                         <script>                       
           
                         // JavaScript program to find the k-th missing element                       
                         // in a given sequence                       
           
                         // Returns k-th missing element. It returns -1 if                       
                         // no k is more than number of missing elements.                       
                         function                                     find(a, b, k, n1, n2)                       
                         {                       
                                                 // Insert all elements of givens sequence b[].                       
                                                 var                                     s =                                     new                                     Set();                       
                                                 for                                     (                                     var                                     i = 0; i < n2; i++)                       
                                                 s.add(b[i]);                       
           
                                                 // Traverse through increasing sequence and                       
                                                 // keep track of count of missing numbers.                       
                                                 var                                     missing = 0;                       
                                                 for                                     (                                     var                                     i = 0; i < n1; i++) {                       
                                                 if                                     (!s.has(a[i]))                       
                                                 missing++;                       
                                                 if                                     (missing == k)                       
                                                 return                                     a[i];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         // driver program to test the above function                       
                         var                                     a = [0, 2, 4, 6, 8, 10, 12, 14, 15];                       
                         var                                     b = [4, 10, 6, 8, 12];                       
                         var                                     n1 = a.length;                       
                         var                                     n2 = b.length;                       
                         var                                     k = 3;                       
                         document.write( find(a, b, k, n1, n2));                       
           
                         </script>                       

输出：

时间复杂性： O（n1+n2） 辅助空间： O（n2）本文由 拉贾·维克拉马蒂亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章