Самый эффективный способ получить самые большие 3 элемента массива

Question

Мне дали массив элементов и встроенную функцию, которая может сортировать 5 элементов одновременно.Как использовать только эту функцию, чтобы получить 3 самых больших элемента массива с наименьшим количеством вызовов этой функции?

Подход, который я попробовал, состоит в том, чтобы разделить массив на группы по 5 человек, применить функцию к каждой группе и применить функцию к максимумам, полученным из каждой группы.

Этот подход не срабатывает, когдасамые высокие и вторые по величине оказываются в той же группе.Есть ли лучший подход для этого?

Answer 1

#include<stdio.h>
#include<limits.h>

int retmax(int *a,int n,int exc){

    int max = INT_MIN;
    for(int i=0;i<n;i++){
        if(a[i] > max && a[i] < exc)
           max = a[i];
    }

    return max;
}

int main(){

    int a[]={32,54,12,43,98,45,87};
    int size = sizeof(a)/sizeof(a[0]);

    int x = retmax(a,size,INT_MAX);
    int y = retmax(a,size,x);
    int z = retmax(a,size,y);

    printf("%d %d %d",x,y,z);
}

Простое решение O (n).

Answer 2

#include <iostream>


void sortThree(int res[3]) {
   for(int j = 0; j < 2; j++) {
      if(res[j] > res[j+1])
         std::swap(res[j], res[j+1]);
}
   if(res[0] > res[1]) std::swap(res[0], res[1]); // second pass
}

bool lsearch(int src[], int n, int k) {
  for(int i = 0; i < n; i++) {
    if(src[i] == k) return true;
  }
  return false;
}

void getThreeLargest(int arr[], int n, int res[3]) {
  res[0] = arr[0];
  res[1] = arr[1];
  res[2] = arr[2];
  sortThree(res);
  for(int i = 3; i < n; i++) {
    // if no repetition wanted
    // if(arr[i] > res[0] && !lsearch(res, 3, arr[i])) {
    if(arr[i] > res[0]) {
      res[0] = arr[i];
      sortThree(res);
    }
  }
}

int main(int argc, char *argv[])
{
  int arr[] = {91,21,3,-4,5,2,1,90,9,11};
  int res[3];
  getThreeLargest(arr, 10, res);
  for(int i = 0; i < 3; i++)
    std::cout << res[i] << '\n';
  return 0;
}

Очень простое решение здесь c-way, чтобы сделать это.Вы можете легко конвертировать его в Java.Сканирование массива O (n).Поскольку небольшой массив для сортировки и поиска содержит только 3 элемента, мы можем легко использовать линейный поиск, чтобы избежать повторения, а сортировка занимает всего 2 сравнения.Это все еще O (n).

Answer 3

Поскольку у вас есть встроенный метод для сортировки пяти элементов, я предлагаю: Сортировать первые пять элементов из массива.Неоднократно отбрасывайте два наименьших из пяти и заменяйте еще два элемента из массива (два элемента, которые еще не рассматривались), а затем снова сортируйте пять.В итоге возьмите наибольшую тройку из пяти.

Можно будет сделать чуть лучше, чем я набросал.Скажем, у вас есть 25 элементов.Для каждой группы из 5 найдите три самых больших.Тогда среди номеров.1 из каждой группы найти три крупнейших.То же самое для номеров.2 от каждой группы и нос.3. Теперь мы можем сделать вывод, что три самых больших в целом будут среди трех самых больших.1, два самых больших номера2 и самый большой нет.3, то есть шесть элементов вместо 9. Таким образом, мы можем найти три самых больших всего за два дополнительных вызова вашего встроенного метода вместо трех дополнительных вызовов.Однако обобщить идею для любого размера исходного массива будет сложно.

Answer 4

Как насчет этого метода.

1. Разделить массив на группы по 5
2. Применить предоставленный метод сортировки для каждой группы из 5 элементов
3. Получить первые 3 элемента из каждого массива
4. Затем объедините идентифицированные 3 элемента в каждой группе в один отдельный массив
5. Теперь повторите процедуру с шага 1 до 4, пока окончательный размер массива не станет меньше или равен 5
6. Получитепервые 3 элемента из окончательного массива

Answer 5

Я не уверен, с чем вы работаете, но самый простой способ решить этот вопрос - что-то вроде этого.

public static void main(String[] args) {
    Integer[] nums = {1, 20, 2, 30, 3, 40, 4};
    Arrays.sort(nums);
    System.out.println(nums[nums.length - 1] + " >> "
            + nums[nums.length - 2] + " >> "
            + nums[nums.length - 3]);
}

Я бы порекомендовал добавить больше информации, чтобы получить лучший ответ.

Надеюсь, это поможет.