配列の最大X値

Question

配列のXの最大グレードの配列、サイズ、および数をとる関数を記述しようとしています。
例えば：

array = { 90,45,77,43,67,88 }, maxGrades = 3 

結果は次のようになります。

retArray = {90,77,88} or {90,88,77} 

私が試みられているもの：

int * GetMaxGrades(int * grades, int size, int maxGrades) 
{ 
    int *retArray; 

    if (maxGrades > size) 
     return grades; 

    retArray = (int*)calloc(sizeof(int) * maxGrades); 

    for (int i = 0; i < size; i++) 
    { 
     for (int j = 0; j < maxGrades; j++) 
      if (grades[i] > retArray[j]) 
      { 
       retArray[j] = grades[i]; 
       break; 
      } 
    } 

    return retArray; 
} 

をしかし、私は{90,88,67}

EDITを復活させていますそのような内部ループを変更すると：

 if (grades[i] > retArray[j]) 
     { 
      if (j + 1 < maxGrades) 
       retArray[j + 1] = retArray[j]; 

      retArray[j] = grades[i]; 
      break; 
     } 

これは問題の一部を解決しましたが、それを行う最良の方法ですか？

Answer 1

gradesアレイに重複が含まれている可能性がある場合は、解決が難しくなります。また、grades配列へのポインタを返すと、呼び出し側は返されたポインタを解放すべきかどうか分からないかもしれないことを忘れないでください。

#include <stdio.h> 
#include <stdlib.h> 

int* GetMaxGrades(int* grades, int size, int maxGrades) { 
    if (maxGrades <= 0 || size <= 0) 
     return NULL; 

    // first, function must allocate memory every time, 
    // otherwise you can't understand when to free memory or when do not it. 
    int *retArray = (int*)malloc(sizeof(int) * maxGrades); 

    if (maxGrades >= size) { 
     for (int i = 0; i < size; ++i) 
      retArray[i] = grades[i]; 
     for (int i = size; i < maxGrades; ++i) 
      retArray[i] = 0; 
    } 
    else { 
     // need to save positions of found max grades, 
     // because if there's duplicates among grades, 
     // you will pick up only different onces. 
     int *positions = (int*)malloc(sizeof(int) * maxGrades); 
     for (int i = 0; i < maxGrades; ++i) { 
      int position = 0; 
      int maxgrade = INT_MIN; 
      for (int j = 0; j < size; ++j) { 
       // pick max grade 
       if (grades[j] > maxgrade) { 
        // do not permit duplicates among positions 
        bool newmax = true; 
        for (int k = 0; k < i; ++k) { 
         if (positions[k] == j) { 
          newmax = false; 
          break; 
         } 
        } 
        // assign new max value & position 
        if (newmax) { 
         position = j; 
         maxgrade = grades[j]; 
        } 
       } 
      } 
      positions[i] = position; 
      retArray[i] = maxgrade; 
     } 
     free(positions); 
    } 
    return retArray; 
} 

int main(int argc, char* argv[]) { 
    int a[] = { 90,45,77,43,67,88 }; 
    const int max_grades = 3; 
    int *p = GetMaxGrades(a, sizeof(a)/sizeof(a[0]), 3); 
    for (int i = 0; i < max_grades; ++i) { 
     printf("%d ", p[i]); 
    } 
    printf("\n"); 
    free(p); 
    return 0; 
} 

あなたは、より簡単になりますqsortを使用することを許可されている場合は、次の

#include <stdio.h> 
#include <stdlib.h> 

int greater_comp(const void * a, const void * b) { 
    return *(int*)b - *(int*)a; 
} 

int* GetMaxGrades(int* grades, int size, int maxGrades) { 
    if (maxGrades <= 0 || size <= 0) 
     return NULL; 

    int alloc_size = (maxGrades < size) ? size : maxGrades; 

    // copy grades array (allocate more memory) 
    int *retArray = (int*)malloc(sizeof(int) * alloc_size); 
    for (int i = 0; i < size; ++i) 
     retArray[i] = grades[i]; 
    for (int i = size; i < alloc_size; ++i) 
     retArray[i] = 0; 

    // sort: descending order 
    qsort(retArray, size, sizeof(int), greater_comp); 

    return retArray; 
} 

int main(int argc, char* argv[]) { 
    int a[] = { 90,45,77,43,67,88 }; 
    const int max_grades = 3; 
    int *p = GetMaxGrades(a, sizeof(a)/sizeof(a[0]), 3); 
    for (int i = 0; i < max_grades; ++i) { 
     printf("%d ", p[i]); 
    } 
    printf("\n"); 
    free(p); 
    return 0; 
} 

そして、あなたは、はるかに容易になるだろうアルゴリズムライブラリを使用する場合：

#include <iostream> 
#include <algorithm> 
#include <functional> 
#include <vector> 

using namespace std; 

vector<int> GetMaxGrades(vector<int> grades, int maxGrades) { 
    // descending order 
    sort(grades.begin(), grades.end(), greater<int>()); 
    grades.resize(maxGrades); 
    return grades; 
} 

int main(int argc, char* argv[]) { 
    vector<int> a = { 90,45,77,43,67,88 }; 
    vector<int> p = GetMaxGrades(a, 3); 
    for (auto& i : p) 
     cout << i << ' '; 
    cout << endl; 
    return 0; 
} 

Answer 2

最後のループ反復の開始時にretArrayは次のようになります。{90,77,67}i=5で内部ループをステップ実行すると、67の前に77が見つかるため、77が置き換えられます。サイズNの配列からXの最大値を選択する

for(...) 
    if(grades[i] > retArray[j]) 
     if(retArray[j] < retArray[minVal]) 
      minVal = j; 
if(minVal > 0) 
    retArray[minVal] = grades[i]; 
minVal = -1; 

Answer 3

O（N）で実行することができます：あなたは、おそらく配列をソートし、トップmaxGrades値を取るが、あなたはそれをあなたの方法をしたい場合はすべきですクイックソートの発明者によるQuickSelectアルゴリズムを使用した平均複雑度：https://en.wikipedia.org/wiki/Quickselect

Answer 4

選択アルゴリズムを使用して線形時間で実行できますが、通常、各繰り返しでトップk要素を格納する最小ヒープを使用して行われます。ヒープ内の最小要素が現在の反復要素より大きいかどうかをチェックし、存在する場合は置換します。

これはO(nlogk)時間であり、余分なメモリしかないため、データを1回だけトラバースする必要があります（エレメントがストリームに入っている場合は完全に機能します）。

次のコードは、C++ 11（エレガントなfor-eachループ）ですが、同じデータ構造を使用して古いC++コードに変換するのは簡単です。

#include <iostream> 
#include <vector> 
#include <queue> 

int main(void) { 
    int array[] = { 90,45,77,43,67,88 }; 
    int maxGrades = 3; 
    std::priority_queue<int, std::vector<int>, std::greater<int>> q; 
    for (int x : array) { 
     // populate first maxGrades elements 
     if (q.size() < maxGrades) { 
      q.push(x); 
     // replace if new element is higher than smallest in heap. 
     } else if (q.top() < x) { 
      q.pop(); 
      q.push(x); 
     } 
    } 
    // print elements 
    std::cout << "elements: "; 
    while (!q.empty()) { 
     std::cout << q.top() << " "; 
     q.pop(); 
    } 
    return 0; 
}