Алгоритм нахождения суммы 2-го, 3-го и 4-го старших чисел из 2 разных массивов

Question

У меня есть 2 очень больших целочисленных массива, скажем, a [] и b [].
Я хочу вычислить сумму 2-го, 3-го и 4-го наибольшего числа из числа a [] и b [].то есть 2-е, 3-е и 4-е старшие числа среди обоих массивов ... это сумма только 3 чисел.Пожалуйста, предложите хороший алгоритм для этой проблемы.

Пожалуйста, поддержите ваш ответ с учетом временной сложности алгоритма.

Примечание: язык программирования не имеет значения.Вы можете предположить, что C

Вот что я разработал для этой задачи
Алгоритм:
1. Рассмотрим массив a [] и b [].Сортируйте a [] и b [] с сортировкой по максимальному значению кучи.
2. Теперь оба массива сортируются с помощью элемента max в качестве корневого узла в обоих массивах.Сравните корневые узлы a [] и b [], в зависимости от того, что больше, удалите это число из массива.
3. Повторно укажите массив, в котором был элемент max.
4. Теперь добавьте корневые узлы из [[] и b [] в переменной скажем sum.
5. Повторно укажите a [] и b [].
6. Сравните корневые узлы a [] и b [], в зависимости от того, что больше, добавьте это число к сумме.
7. Распечатать сумму вариации.

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 номера, так зачем же дополнительная работа?

Answer 2

O(n) в питоне:

def biggestn(n, array):
   arr=[]
   for x in array:
      arr=insert(arr,x)[0:n] #use insertion sort to insert x into arr here for speed 
   return sum(arr)

Для двух массивов просто biggestn(4, a++b)

Answer 3

Наивное решение (которое я не рекомендую) состоит в том, чтобы сначала отсортировать, а затем добавить 3 элемента.Предполагая разумный алгоритм сортировки, это будет O(n*log(n)).

. Лучшим решением, которое обобщает более 3 элементов, было бы внедрение одного из нескольких алгоритмов выбора на основе сортировки выбораили быстрая сортировка.В зависимости от того, что именно нужно делать, они могут приближаться к линейному времени.