ในปัญหาที่กำหนด เราจำเป็นต้องจัดอันดับองค์ประกอบที่กำหนดทั้งหมดของอาร์เรย์ โดยตัวเลขที่น้อยที่สุดจะมีอันดับที่น้อยที่สุด และจำนวนที่ใหญ่ที่สุดมีอันดับที่ใหญ่ที่สุด เรายังจำเป็นต้องเปลี่ยนลำดับของตัวเลขตามความถี่ ตัวอย่างเช่น −
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 ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ