資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 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
查詢解決方案的方法
有兩種不同的方法可以找到解決方案，它們是 -
暴力方法
在這種方法中，我們將迴圈，選擇任何特定元素，並確定其排名。
示例
#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] << ' ';
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 並累加到我們的排名總和中。當我們的元素髮生變化時，我們將排名分配給先前的元素，重新整理 s 和總計，並繼續我們的程式碼。
結論
在本文中，我們解決了一個問題，即查詢陣列中所有元素的排名。我們還學習了此問題的 C++ 程式以及我們解決此問題的完整方法（普通和高效）。我們可以在其他語言（如 C、Java、Python 和其他語言）中編寫相同的程式。
更新於：2021-11-26
1K+ 閱讀量
廣告