นับองค์ประกอบน้อยกว่าด้านขวาโดยใช้ Set ใน C++ STL

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมนับองค์ประกอบที่น้อยกว่าด้านขวา (smaller elements on right side) โดยใช้ set ใน C++ STL

ให้อาร์เรย์หนึ่ง เราต้องสร้างอาร์เรย์ใหม่ที่แต่ละตำแหน่งเก็บจำนวนองค์ประกอบที่น้อยกว่าองค์ประกอบปัจจุบันและอยู่ทางขวา

ตัวอย่างโค้ด

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

void count_Rsmall(int A[], int len) {
    set<int> s;
    int countSmaller[len];
    for (int i = len - 1; i >= 0; i--) {
        s.insert(A[i]);
        auto it = s.lower_bound(A[i]);
        countSmaller[i] = distance(s.begin(), it);
    }
    for (int i = 0; i < len; i++)
        cout << countSmaller[i] << " ";
}

int main() {
    int A[] = {12, 1, 2, 3, 0, 11, 4};
    int len = sizeof(A) / sizeof(int);
    count_Rsmall(A, len);
    return 0;
}

เอาต์พุต

6 1 1 1 0 1 0