Hướng giải của Rời rạc hoá mảng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Sao chép mảng A, sắp xếp và loại bỏ các phần tử trùng nhau để có mảng các giá trị phân biệt. Với mỗi phần tử trong A, dùng tìm kiếm nhị phân (lower_bound) để tìm thứ hạng 0-based của nó trong mảng đã nén.

Độ phức tạp: O(N log N) thời gian, O(N) bộ nhớ.

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for (int x : a) {
        int idx = lower_bound(b.begin(), b.end(), x) - b.begin();
        cout << idx << ' ';
    }
    return 0;
}

Python

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    b = sorted(set(a))

    for x in a:
        idx = bisect.bisect_left(b, x)
        print(idx, end=' ')

if __name__ == '__main__':
    main()

Nhận xét

Không có ý kiến tại thời điểm này.