C++ で記述された配列要素のソートのランキング

指定された問題では、配列の指定されたすべての要素をランク付けする必要があります。最小の数値は最小のランクを持ち、最大の数値は最大のランクを持ちます。たとえば、数値の頻度に基づいて数値のランキングを変更する必要もあります。 -

Input : 20 30 10
Output : 2.0 3.0 1.0

Input : 10 12 15 12 10 25 12
Output : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0

Here the rank of 10 is 1.5 because there are two 10s present in the given array now if we assume they both take different ranks i.e. 1 and 2 and we thus divide it within themselves so their rank becomes 1.5 and 1.5.

Input : 1, 2, 5, 2, 1, 60, 3
Output : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0

解決策を見つける方法

解決策を見つける方法は 2 つあります。

ブルートフォースメソッド

このメソッドでは、ループして特定の要素を選択し、そのランキングを決定します。

例

#include <bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = {1, 2, 5, 2, 1, 25, 2}; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our given array

   float rank[n] = {0}; // our ranking array
   for (int i = 0; i < n; i++) {
      int r = 1; // the number of elements greater than arr[i]
      int s = 1; // the number of elements equal to arr[i]

      for (int j = 0; j < n; j++) {
         if (j != i && arr[j] < arr[i])
            r += 1;
   
         if (j != i && arr[j] == arr[i])
            s += 1;
      }
      rank[i] = r + (float)(s - 1) / (float) 2; // using formula
      //to obtain rank of particular element

   }

   for (int i = 0; i < n; i++) // outputting the ranks
      cout << rank[i] << &#39; &#39;;

   return 0;
}

出力

1.5 4 6 4 1.5 7 4

このプログラムの時間計算量はO(N*N)です。Nは指定された配列の現在のサイズです。 ; ご覧のとおり、時間の複雑さは良くないので、より高い制約に適合するように効率を高めます。

効率的な方法

この方法では、新しい配列を取得して並べ替えます。配列は並べ替えられているため、同じランクを持つすべての要素が一緒になることがわかります。通常どおりそれらをランク付けしてから、特定の要素のランクを計算します。

例

#include <bits/stdc++.h>

using namespace std;

int main() {
   int arr[] = {1, 2, 5, 2, 1, 60, 3}; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our given array
   float rank[n] = {0}; // our ranking array
   int old[n];
   for(int i = 0; i < n; i++)
   old[i] = arr[i];
   sort(arr, arr+n); // sorting the array
   int prev = arr[0];
   int r = 1; // ranks
   int s = 0; // frequency
   int tot = 0; // will stack up all the rank contained by an element
   map<int, float> rrank;

   for (int i = 0; i < n; i++) {
      if(prev == arr[i]) {
         s++;
         tot += r;
      } else {
         float now = 0;
         now = (float)tot/s; // dividing the ranks equally
         rrank[prev] = now;
         prev = arr[i];
         tot = r;
         s = 1;
      }
      r++;
   }
   rrank[arr[n-1]] = (float)tot/s;
   for (int i = 0; i < n; i++) // outputting the ranks
      cout << rrank[old[i]] << " ";

   return 0;
}

出力

1.5 3.5 6 3.5 1.5 7 5

上記コードの説明

このメソッドでは、配列をソートし、各要素の先頭から開始します。がランク付けされます（ランキングは1から始まります）。ここで、前の要素が現在の要素と等しい場合、 s をインクリメントし、ランク合計に追加します。要素が変更されると、前の要素のランクを分離し、 と合計を更新して、コードを続行します。

結論

この記事では、配列内のすべての要素のランキングを見つける問題を解決しました。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを、C、Java、Python などの他の言語で作成できます。

以上がC++ で記述された配列要素のソートのランキングの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。