การหา Rank ของทุกองค์ประกอบในอาร์เรย์โดยใช้ C++

ในปัญหานี้ เราต้องหา rank ของทุกองค์ประกอบในอาร์เรย์ที่กำหนด โดยตัวเลขที่น้อยที่สุดจะมี rank ที่น้อยที่สุด และตัวเลขที่มากที่สุดจะมี rank ที่มากที่สุด เรายังต้องปรับ rank ของตัวเลขตามความถี่ของมัน ตัวอย่างเช่น:

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
ที่นี่ rank ของ 10 คือ 1.5 เพราะมี 10 อยู่สองตัวในอาร์เรย์ ถ้าสมมติว่าทั้งสองตัวได้ rank ต่างกันคือ 1 และ 2 แล้วนำมาหารกัน rank จะกลายเป็น 1.5 และ 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

วิธีการแก้ปัญหา

มีสองวิธีการที่แตกต่างกันในการหาคำตอบ:

วิธี Brute Force (วิธีขั้นพื้นฐาน)

ในวิธีนี้ เราจะวนลูป เลือกองค์ประกอบเฉพาะเจาะจง และกำหนด rank ของมัน

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 25, 2}; // อาร์เรย์ที่กำหนด
    int n = sizeof(arr) / sizeof(arr[0]); // ขนาดของอาร์เรย์
    float rank[n] = {0}; // อาร์เรย์สำหรับเก็บ rank
    
    for (int i = 0; i < n; i++) {
        int r = 1; // จำนวนองค์ประกอบที่น้อยกว่า arr[i]
        int s = 1; // จำนวนองค์ประกอบที่เท่ากับ 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; // ใช้สูตรเพื่อหา rank
    }
    
    for (int i = 0; i < n; i++) // แสดงผล rank
        cout << rank[i] << ' ';
    return 0;
}

ผลลัพธ์

1.5 4 6 4 1.5 7 4

โปรแกรมนี้มีความซับซ้อนด้านเวลา O(N²) โดยที่ N คือขนาดของอาร์เรย์ที่กำหนด ตอนนี้คุณเห็นได้ว่าความซับซ้อนด้านเวลาของเราไม่ดี ดังนั้นเราจะเพิ่มประสิทธิภาพเพื่อให้ทำงานได้ดีกับข้อจำกัดที่สูงกว่า

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะนำอาร์เรย์ใหม่ไปจัดเรียง ตอนนี้อาร์เรย์ถูกจัดเรียงแล้ว เรารู้ว่าองค์ประกอบที่มี rank เดียวกันจะอยู่ติดกัน ดังนั้นเราจึงให้ rank ตามปกติ จากนั้นคำนวณ rank ขององค์ประกอบเฉพาะเจาะจง

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 60, 3}; // อาร์เรย์ที่กำหนด
    int n = sizeof(arr) / sizeof(arr[0]); // ขนาดของอาร์เรย์
    float rank[n] = {0}; // อาร์เรย์สำหรับเก็บ rank
    int old[n];
    
    for(int i = 0; i < n; i++)
        old[i] = arr[i];
    
    sort(arr, arr+n); // จัดเรียงอาร์เรย์
    
    int prev = arr[0];
    int r = 1; // rank
    int s = 0; // ความถี่
    int tot = 0; // จะสะสม rank ทั้งหมดที่องค์ประกอบมี
    map rrank;
    
    for (int i = 0; i < n; i++) {
        if(prev == arr[i]) {
            s++;
            tot += r;
        } else {
            float now = 0;
            now = (float)tot/s; // แบ่ง rank อย่างเท่าเทียม
            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++) // แสดงผล rank
        cout << rrank[old[i]] << " ";
    return 0;
}

ผลลัพธ์

1.5 3.5 6 3.5 1.5 7 5

คำอธิบายโค้ด

ในวิธีนี้ เราจัดเรียงอาร์เรย์ของเรา จากนั้นเราให้ rank แต่ละองค์ประกอบตั้งแต่ต้น (rank เริ่มจาก 1) ตอนนี้ หากองค์ประกอบก่อนหน้าเท่ากับองค์ประกอบปัจจุบัน เราเพิ่ม s และสะสมผลรวมของ rank เมื่อองค์ประกอบเปลี่ยน เราแบ่ง rank ให้กับองค์ประกอบก่อนหน้า รีเซ็ต s และ total แล้วดำเนินการต่อ

สรุป

ในบทความนี้ เราแก้ปัญหาการหา Rank ของทุกองค์ประกอบในอาร์เรย์ เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้