获取数组中最大 3 个元素的最有效方法

Question

我得到了一个元素数组和一个可以一次对 5 个元素进行排序的内置函数。如何仅使用此函数以最少的调用次数获取数组中最大的 3 个元素？

我尝试过的方法是将数组分成每组 5 组，对每组应用该函数，并对从每组获得的最大值应用该函数。

当最高值和第二高值恰好出现在同一组中时，这种方法就会失败。有更好的方法来做到这一点吗？

Answer 1

由于您有内置方法对五个元素进行排序，我建议：对数组中的前五个元素进行排序。反复丢弃五个中最小的两个，并用数组中的另外两个元素替换（尚未考虑的两个元素），然后再次对五个进行排序。最后取五个中最大的三个。

有可能比我画的草图做得更好一点。假设您有 25 个元素。每组 5 个，找出其中最大的三个。然后在其中。 1 从每组中找出三个最大的。编号相同。每组2个，编号。 3. 现在我们可以推断，总体上最大的三个将属于最大的三个。 1、最大的两个号。 2 和单个最大的编号。 3，即 6 个元素，而不是 9 个。因此，我们只需再调用内置方法两次（而不是再调用 3 次）即可找到最大的三个元素。不过，将这个想法推广到任何大小的原始数组都会很复杂。

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 方式实现。您可以轻松地将其转换为java。扫描数组的时间复杂度为 O(n)。由于要排序和搜索的小数组只有 3 个元素，我们可以轻松地使用线性搜索来避免重复，并且排序只需要 2 次比较。仍然是 O(n)。

Answer 3

这个方法怎么样？

1. 将数组分成 5 组
2. 对每组 5 个元素应用提供的排序方法
3. 获取每个数组的前 3 个元素
4. 然后将每组中识别出的 3 个元素合并到一个数组中
5. 现在重复步骤1到4，直到最终数组大小小于或等于5
6. 从最终数组中获取前 3 个元素

Answer 4

公开课测试{

public static void main(String[] args) throws Exception{
 
 int[] arr={7,18,92,72,29,57};
 
 int first,second,third;
 
 first=second=third=Integer.MIN_VALUE;
 
 for(int i=0;i<arr.length;i++){
   if(arr[i]>first){
     third=second;
     second=first;
     first=arr[i];
   }else if(arr[i]>second){
     third=second;
     second=arr[i];
     
   }else{
     third=arr[i];
   }
 }
 System.out.println(""+first+"\t"+second+"\t"+third);

}

}

Answer 5

#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) 解决方案。