Rangfolge der in C++ geschriebenen Array-Elementsortierung

In der gegebenen Aufgabe müssen wir alle gegebenen Elemente des Arrays in eine Rangfolge bringen, wobei die kleinste Zahl den kleinsten Rang und die größte den größten Rang hat. Zum Beispiel müssen wir auch die Rangfolge der Zahlen basierend auf ihrer Häufigkeit ändern –

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

Methode zum Finden einer Lösung

Es gibt zwei verschiedene Methoden zum Finden einer Lösung, nämlich –

Brute-Force-Methode

Bei dieser Methode haben wir führt eine Schleife durch, wählt ein bestimmtes Element aus und bestimmt seine Rangfolge.

Beispiel

#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;
}

Ausgabe

1.5 4 6 4 1.5 7 4

Die Zeitkomplexität dieses Programms beträgt O(N*N), wobei N jetzt die Größe des gegebenen Arrays ist; unsere Zeitkomplexität ist also nicht gut Wir werden seine Effizienz verbessern, um uns besser an höhere Einschränkungen anzupassen.

Effiziente Methode

Bei dieser Methode nehmen wir ein neues Array und sortieren es. Da das Array sortiert ist, wissen wir jetzt, dass alle Elemente mit demselben Rang zusammen sein werden, also führen wir sie jetzt wie gewohnt aus Berechnen Sie dann den Rang eines bestimmten Elements.

Beispiel

#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;
}

Ausgabe

1.5 3.5 6 3.5 1.5 7 5

Erklärung des obigen Codes

Bei dieser Methode sortieren wir das Array und ordnen dann jedes Element von Anfang an (die Rangfolge beginnt bei 1). Wenn nun unser vorheriges Element gleich dem aktuellen Element ist, erhöhen wir s und addieren es zu unserer Rangsumme. Wenn sich unser Element ändert, trennen wir die Ränge des vorherigen Elements, aktualisieren s und die Gesamtzahl und fahren mit unserem Code fort.

Fazit

In diesem Artikel haben wir ein Problem gelöst, um die Rangfolge aller Elemente in einem Array zu ermitteln. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben.

Das obige ist der detaillierte Inhalt vonRangfolge der in C++ geschriebenen Array-Elementsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!