在由两个数组之和构成的集合中查找第N项-yiteyi-C++库

给定两个排序数组，我们可以得到一组和（第一个数组加一个元素，第二个数组加一个元素）。在按排序顺序考虑的已形成集合的元素中找到第N个元素。注：和的集合应该有唯一的元素。

null

例如：

Input: arr1[] = {1, 2}        arr2[] = {3, 4}        N = 3Output: 6We get following elements set of sums.4(1+3), 5(2+3 or 1+4), 6(2+4)Third element in above set is 6.Input: arr1[] = { 1,3, 4, 8, 10}         arr2[] = {20, 22, 30, 40}         N = 4Output: 25We get following elements set of sums.21(1+20), 23(1+22 or 20+3), 24(20+4), 25(22+3)...Fourth element is 25.

问：微软采访

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

方法：

运行两个循环——第一个用于第一个阵列，第二个用于第二个阵列。
只需考虑每一对，并将它们的总和存储在一个自平衡BST中（这是通过C++中的SET和MAP实现）。
我们使用C++中的SET，因为我们只需要看到元素是否存在或不存在，我们不需要密钥，值对。
遍历集合并返回集合中的第n个元素。

以下是上述方法的实施情况：

C++

                         // C++ program to find N'th element in a set formed                       
                         // by sum of two arrays                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         //Function to calculate the set of sums                       
                         int                                     calculateSetOfSum(                                     int                                     arr1[],                                     int                                     size1,                                     int                                     arr2[],                       
                                                 int                                     size2,                                     int                                     N)                       
                         {                       
                                                 // Insert each pair sum into set. Note that a set                       
                                                 // stores elements in sorted order and unique elements                       
                                                 set<                                     int                                     > s;                       
                                                 for                                     (                                     int                                     i=0 ; i < size1; i++)                       
                                                 for                                     (                                     int                                     j=0; j < size2; j++)                       
                                                 s.insert(arr1[i]+arr2[j]);                       
           
                                                 // If set has less than N elements                       
                                                 if                                     (s.size() < N)                       
                                                 return                                     -1;                       
           
                                                 // Find N'tb item in set and return it                       
                                                 set<                                     int                                     >::iterator it = s.begin();                       
                                                 for                                     (                                     int                                     count=1; count<N; count++)                       
                                                 it++;                       
                                                 return                                     *it;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = {1, 2};                       
                                                 int                                     size1 =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     arr2[] = {3, 4};                       
                                                 int                                     size2 =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
           
                                                 int                                     N = 3;                       
                                                 int                                     res = calculateSetOfSum(arr1, size1, arr2, size2, N);                       
                                                 if                                     (res == -1)                       
                                                 cout <<                                     "N'th term doesn't exists in set"                                     ;                       
                                                 else                       
                                                 cout <<                                     "N'th element in the set of sums is "                       
                                                 << res;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find N'th element in a set formed                       
                         // by sum of two arrays                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to calculate the set of sums                       
                         static                                     int                                     calculateSetOfSum(                                     int                                     arr1[],                                     int                                     size1,                                     int                                     arr2[],                       
                                                 int                                     size2,                                     int                                     N)                       
                         {                       
                                                 // Insert each pair sum into set. Note that a set                       
                                                 // stores elements in sorted order and unique elements                       
                                                 SortedSet<Integer> s =                                     new                                     TreeSet<Integer>();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < size1; i++)                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < size2; j++)                       
                                                 s.add(arr1[i]+arr2[j]);                       
           
                                                 // If set has less than N elements                       
                                                 if                                     (s.size() < N)                       
                                                 return                                     -                                     1                                     ;                       
           
                                                 // Find N'tb item in set and return it                       
                                   
                                                 return                                     (                                     int                                     )s.toArray()[ N-                                     1                                     ];                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     arr1[] = {                                     1                                     ,                                     2                                     };                       
                                                 int                                     size1 = arr1.length;                       
                                                 int                                     arr2[] = {                                     3                                     ,                                     4                                     };                       
                                                 int                                     size2 = arr2.length;                       
           
                                                 int                                     N =                                     3                                     ;                       
                                                 int                                     res = calculateSetOfSum(arr1, size1, arr2, size2, N);                       
                                                 if                                     (res == -                                     1                                     )                       
                                                 System.out.println(                                     "N'th term doesn't exists in set"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "N'th element in the set of sums is "                       
                                                 +res);                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

C#

                         // C# program to find N'th element in                       
                         // a set formed by sum of two arrays                       
                         using                                     System;                       
                         using                                     System.Linq;                       
                         using                                     System.Collections.Generic;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         // Function to calculate the set of sums                       
                         static                                     int                                     calculateSetOfSum(                                     int                                     []arr1,                                     int                                     size1,                       
                                                 int                                     []arr2,                                     int                                     size2,                       
                                                 int                                     N)                       
                         {                       
                                                 // Insert each pair sum into set.                       
                                                 // Note that a set stores elements in                       
                                                 // sorted order and unique elements                       
                                                 HashSet<                                     int                                     > s =                                     new                                     HashSet<                                     int                                     >();                       
                                                 for                                     (                                     int                                     i = 0; i < size1; i++)                       
                                                 for                                     (                                     int                                     j = 0; j < size2; j++)                       
                                                 s.Add(arr1[i] + arr2[j]);                       
           
                                                 // If set has less than N elements                       
                                                 if                                     (s.Count < N)                       
                                                 return                                     -1;                       
           
                                                 // Find N'tb item in set and return it                       
                                                 int                                     []last = s.ToArray();                       
                                                 return                                     last[s.Count - 1];                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     []arr1 = {1, 2};                       
                                                 int                                     size1 = arr1.Length;                       
                                                 int                                     []arr2 = {3, 4};                       
                                                 int                                     size2 = arr2.Length;                       
           
                                                 int                                     N = 3;                       
                                                 int                                     res = calculateSetOfSum(arr1, size1,                       
                                                 arr2, size2, N);                       
                                                 if                                     (res == -1)                       
                                                 Console.WriteLine(                                     "N'th term doesn't exists in set"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "N'th element in the set"                                     +                       
                                                 " of sums is "                                     + res);                       
                         }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                         // Javascript program to find N'th                       
                         // element in a set formed                       
                         // by sum of two arrays                       
           
                         // Function to calculate the set of sums                       
                         function                                     calculateSetOfSum(arr1, size1,                       
                                                 arr2, size2, N)                       
                         {                       
                                   
                                                 // Insert each pair sum into set.                       
                                                 // Note that a set stores elements                       
                                                 // in sorted order and unique elements                       
                                                 let s =                                     new                                     Set();                       
                                                 for                                     (let i = 0; i < size1; i++)                       
                                                 for                                     (let j = 0; j < size2; j++)                       
                                                 s.add(arr1[i]+arr2[j]);                       
                                   
                                                 // If set has less than N elements                       
                                                 if                                     (s.size < N)                       
                                                 return                                     -1;                       
                                   
                                                 // Find N'tb item in set and return it                       
                                                 return                                     Array.from(s)[N - 1];                       
                         }                       
           
                         // Driver code                       
                         let arr1 = [ 1, 2 ];                       
                         let size1 = arr1.length;                       
                         let arr2 = [ 3, 4 ];                       
                         let size2 = arr2.length;                       
                         let N = 3;                       
           
                         let res = calculateSetOfSum(arr1, size1,                       
                                                 arr2, size2, N);                       
                         if                                     (res == -1)                       
                                                 document.write(                                     "N'th term doesn't "                                     +                       
                                                 "exists in set"                                     );                       
                         else                       
                                                 document.write(                                     "N'th element in the set "                                     +                       
                                                 "of sums is "                                     + res);                       
           
                         // This code is contributed by rag2127                       
           
                         </script>                       

输出

N'th element in the set of sums is 6

时间复杂性： O（mn log（mn）），其中m是第一个数组的大小，n是第二个数组的大小。

本文由 萨希尔·查布拉（阿克库） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章