Trong bài toán đã cho, chúng ta cần xếp hạng tất cả các phần tử đã cho của một mảng, trong đó số nhỏ nhất có hạng nhỏ nhất và số lớn nhất có hạng lớn nhất. Chúng ta cũng cần thay đổi thứ hạng của một số tùy thuộc vào tần số của chúng, chẳng hạn như -
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
Phương pháp tiếp cận để tìm ra giải pháp
Có hai cách tiếp cận khác nhau để tìm ra giải pháp và chúng -
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận này, chúng tôi sẽ lặp lại, chọn bất kỳ phần tử cụ thể nào và xác định thứ hạng của nó.
Ví dụ
#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;
} Đầu ra
1.5 4 6 4 1.5 7 4
Chương trình này có độ phức tạp về thời gian là O (N * N) với N là kích thước của một mảng đã cho bây giờ; như bạn có thể thấy, độ phức tạp về thời gian của chúng tôi không tốt, vì vậy chúng tôi sẽ tăng hiệu quả của nó để làm việc tốt cho các ràng buộc cao hơn.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng ta sẽ lấy một mảng mới và sắp xếp nó ngay bây giờ vì mảng được sắp xếp bây giờ, chúng ta biết rằng tất cả các phần tử có cùng thứ hạng sẽ ở cùng nhau, vì vậy bây giờ chúng ta xếp hạng chúng như bình thường và sau đó tính thứ hạng của một phần tử cụ thể.
Ví dụ
#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;
} Đầu ra
1.5 3.5 6 3.5 1.5 7 5
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng tôi sắp xếp mảng của mình và sau đó chúng tôi xếp hạng từng phần tử từ đầu (xếp hạng bắt đầu từ 1). Bây giờ, nếu phần tử trước của chúng tôi bằng phần tử hiện tại của chúng tôi, chúng tôi tăng s và xếp chồng lên tổng các cấp của chúng tôi. Khi các phần tử của chúng tôi bị thay đổi, chúng tôi chia thứ hạng cho các phần tử trước đó, làm mới các phần tử và tổng số, và tiếp tục mã của chúng tôi.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm Xếp hạng của tất cả các phần tử trong một mảng. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác.