получить n-е наибольшее число

Question

Я пытаюсь получить n-е наибольшее число массива, я пытался отсортировать массив, а затем получить доступ к n-му номеру путем индексации;Я написал этот код:

#include <iostream>
using namespace std;
int largest(int a[],int k){

   for (int i=0;i<=(sizeof(a)/sizeof(*a));i++){
      for (int j=i+1;j<=(sizeof(a)/sizeof(*a));j++){

         if(a[j]>a[i]){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
         }
      }
   }
   return a[k-1];
}

int main()
{
   int a[]={3,2,1,0,5,10};
   int m=largest(a,4);
   cout<<m<<endl;

   return 0;
}

, и когда я распечатываю m, это кажется 5, в то время как ожидается, что будет 2, когда я пытался заменить int m=largest(a,4); на m=largest(a,1);, это напечатало2 так получается, что он печатает индекс массива a, но без сортировки, есть идеи?

Answer 1

UPD: Существует алгоритм STL для использования: std :: nth_element.

#include <iostream>
#include <algorithm>
int main(){
    int arr[] = {54, 897, 87, 4, 6,987};
    size_t length = 6, k = 3;
    std::cout<<std::nth_element(arr, arr + k, arr + length, std::greater<int>());
}

Кроме того, если вы хотите реализовать его самостоятельно, вы можете сделать это на основе быстрогосортировка:

#include <iostream>
#include <algorithm>

template<class T>
T largest_k(T* a, size_t left, size_t right, size_t k) {
  if(left>=right)
    return a[k-1];

  size_t i = left, j = right;   

  T middle = a[ i + (j-i) / 2 ];    

  do {
    while ( a[i] > middle ) i++;
    while ( a[j] < middle ) j--;

    if (i <= j) {
      std::swap(a[i], a[j]);
      i++; j--;
    }
  } while ( i<=j );

  // We need to go deeper only for needed part of a
  if ( k<=j+1 )
    return largest_k(a, left, j, k);
  if ( k>= i ) 
    return largest_k(a, i, right, k);
}

int main()
{
  int arr[] = {54, 897, 87, 4, 6,987};
  size_t length = 6, k = 3;
  std::cout<<largest_k<int>(arr, 0, length-1, k);
}

Answer 2

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int a[]={3,2,1,0,5,10};
   std::sort(a, a+6, greater<int>() );  // Sort an array of 6 elements in greatest-first order.
   cout<<a[3]<<endl;                    // Show the 4th element from the front.

   return 0;
}

Answer 3

Есть три проблемы с вашим кодом.

Во-первых, когда вы передаете массив в качестве аргумента своей функции, он распадается на указатель.Таким образом, функция никогда не сможет узнать размер массива без дополнительной информации.Задача main() состоит в том, чтобы найти размер массива и передать эту информацию в largest().

Во-вторых, в вашем коде возникла ошибка, потому что вы пытаетесьитерировать от 0 до количества элементов в массиве.

Будет работать следующее:

#include <iostream>
using namespace std;
int largest(int a[],int k, int n){
   for (int i = 0; i < n; i++){
      for (int j = i + 1; j < n; j++){
         if (a[j] > a[i]){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
         }
      }
   }
   return a[k-1];
}

int main()
{
   int a[] = {3, 2, 1, 0, 5, 10};
   int k = 4;
   int m = largest(a, k, sizeof a/ sizeof *a);
   cout << m << endl;
}

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

Вы можете сделать копию исходного массива и отсортировать ее.Или вы можете реализовать алгоритм сортировки по k-элементам.В любом случае вам не следует изменять пользовательские данные, просто чтобы найти из них статистику.

Answer 4

Проблема заключается в использовании sizeof(a)/sizeof(*a) для получения количества элементов массива.sizeof(a) - это размер указателя.

Вам необходимо передать размер массива в функцию.

int largest(int a[], int size, int k){

   for (int i=0;i<size;i++){
      for (int j=i+1;j<size;j++){

      ...
      }
   }
}

и вызвать его с помощью

int m = largest(a, 6, 4);