从2个不同数组中找出第2,第3和第4最高数之和的算法

Question

我有2个非常大的整数数组,如a []和b [].
我想计算[]和b []中第2,第3和第4最高数的总和.即两个阵列中的第2,第3和第4最高数字......这只是3个数字的总和.请为此问题建议一个好的算法.

考虑到算法的时间复杂度,请支持您的答案.

注意:编程语言不是问题.你可以假设C.

以下是我为此问题开发的
算法:
1.考虑数组a []和b [].使用最大堆排序对[]和b []进行排序.
2.这两个数组现在都以数组中的最大元素作为根节点进行排序.比较[]和b []的根节点,无论哪个更大,都从数组中删除该数字.
3.重新定义具有max元素的数组.
4.现在在变量say sum中添加[]和b []的根节点.
5.重新合并[]和b [].
6.比较a []和b []的根节点,无论哪个更大,都将该数字加到sum.
7.打印varibale总和.

Answer 1

由于数组未排序,因此您必须至少检查一次每个数字,因此您有一个O(n)的下限,其中n是数字的总数.我相信你可以在O(n)中做到.

时间:O(n)

空间:O(1)

int sum = 0;
int no1 = 0;
int no2 = 0;
int no3 = 0;
int no4 = 0;

int n =  a.size();

for ( int i = 0 ; i < n ; i++ )
{
   if ( a[i] >= no1 )
   {
      no4 = no3; no3 = no2; no2 = no1; no1 = a[i];
   }
   else if ( a[i] >= no2 )
   {
      no4 = no3; no3 = no2; no2 = a[i];
   }
   else if ( a[i] >= no3 )
   {
      no4 = no3; no3 = a[i];
   }
   else if ( a[i] > no4 )
   {
      no4 = a[i];
   } 
}

// Repeat the n =  a[].lenght; for ( int i = 0 ; i < n ; i++ ){...}
// but using the b[] array instead of the a[]

sum = no2 + no3 + no4;

排序是低效的,因为你只需要3个数字,那么为什么额外的工作呢？