Kedudukan pengisihan elemen tatasusunan yang ditulis dalam C++

Dalam masalah yang diberikan, kita perlu menyusun semua elemen tatasusunan yang diberikan, nombor terkecil mempunyai pangkat terkecil dan yang terbesar mempunyai pangkat terbesar. Sebagai contoh, kita juga perlu menukar kedudukan nombor berdasarkan kekerapannya -

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

Kaedah mencari penyelesaian

Terdapat dua kaedah yang berbeza untuk mencari penyelesaian, iaitu -

Kaedah brute force

Dalam kaedah ini, kita akan gelung, pilih mana-mana elemen tertentu dan tentukan kedudukannya.

Contoh

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

Output

1.5 4 6 4 1.5 7 4

Kerumitan masa program ini ialah O(N*N), di mana N ialah saiz tatasusunan yang diberikan sekarang; seperti yang anda lihat, kerumitan masa kita tidak bagus, jadi kami akan meningkatkan kecekapannya untuk menyesuaikan diri dengan lebih baik kepada kekangan yang lebih tinggi.

Kaedah yang cekap

Dalam kaedah ini kita akan mengambil tatasusunan baru dan menyusunnya, memandangkan tatasusunan itu diisih, kini kita tahu bahawa semua elemen dengan pangkat yang sama akan bersama-sama, jadi sekarang kita melakukannya seperti biasa Pangkat, dan kemudian hitung pangkat unsur tertentu.

Contoh

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

Output

1.5 3.5 6 3.5 1.5 7 5

Penjelasan kod di atas

Dalam kaedah ini, kami mengisih tatasusunan dan kemudian menyusun setiap elemen dari awal (kedudukan bermula dari 1). Sekarang, jika elemen kami sebelumnya adalah sama dengan elemen semasa, kami menambah s dan menambah jumlah pangkat kami. Apabila elemen kami berubah, kami memisahkan kedudukan elemen sebelumnya, muat semula s dan jumlahnya, dan teruskan dengan kod kami.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah untuk mencari kedudukan semua elemen dalam tatasusunan. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain, seperti C, java, python dan bahasa lain.

Atas ialah kandungan terperinci Kedudukan pengisihan elemen tatasusunan yang ditulis dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!