#10 LeetCodeDaily - Bài này khó quá nh?ng t?i ?? làm ???c!

Sau chu?i bài bit manipulation là nh?ng bài d?ng s? và m?ng khó nh?n, ch? kh?ng có d? th? tí nào.

?? bài

2070. Most Beautiful Item for Each Query

Cho 1 m?ng 2 chi?u items t?i ?ó mà m?i item = [price, beauty] (có th? coi nh? là giá và ch?t l??ng c?a m?t món hàng).

Cho m?ng queries, v?i m?i ph?n t? queries[i] trong m?ng queries, l?y ra beauty c?a item có beauty cao nh?t và price <= queries[i]. N?u kh?ng có tho? m?n thì l?y 0.

Tr? v? m?ng k?t qu? queries t??ng ?ng.

Y t??ng

VD: items = [[1,5],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]

• S?p x?p m?ng items theo price t?ng d?n, n?u price b?ng nhau thì s?p x?p theo beauty gi?m d?n.

Sau ?ó items = [[1,5],[2,4],[3,5],[3,2],[5,6]]

• ?i t? ??u m?ng ??n cu?i, n?u item ??ng tr??c có beauty l?n h?n beauty c?a item ??ng sau, gán beauty c?a item ??ng sau b?ng beauty c?a item ??ng tr??c.

Sau ?ó items = [[1,5],[2,5],[3,5],[3,5],[5,6]]

• V?i m?i ph?n t? queries[i], tìm ki?m item có price là l?n nh?t và nh? h?n ho?c b?ng queries[i]. N?u kh?ng tìm ???c thì k?t qu? là 0. Gán l?i k?t qu? vào queries[i].

Sau ?ó queries = [5,5,5,5,6,6]

Tri?n khai

• S?p x?p: t?i s? d?ng Array.sort() c?a java vì t?i l??i vi?t l?i gi?i thu?t s?p x?p.
• Bi?n maxBeauty ?? l?u beauty cao nh?t c?a các items phía tr??c
• L?p qua m?ng items m?t l?n n?a, n?u items phía sau có beauty < maxBeauty, t?i gán l?i beauty c?a items phía sau là maxBeauty. Ng??c l?i thì t?i gán l?i maxBeauty m?i.
• L?p qua m?ng queries, v?i m?i queries[i], t?i dùng tìm ki?m nh? phan ?? tìm ra items có price là l?n nh?t và nh? h?n ho?c b?ng queries[i], kh?ng tìm th?y thì k?t qu? là 0.

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {

        Arrays.sort(items, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return Integer.compare(o1[0], o2[0]);
            } else {
                return Integer.compare(o2[1], o1[1]);
            }
        });
        int maxBeauty = items[0][1];
        for (int i = 0; i < items.length; i++) {
            if (maxBeauty > items[i][1]) {
                items[i][1] = maxBeauty;
            } else {
                maxBeauty = items[i][1];
            }
        }
        for (int i = 0; i < queries.length; i++) {
            queries[i] = search(queries[i], items);
        }
        return queries;
    }

    private int search(int query, int[][] items) {
        if (query < items[0][0]) {
            return 0;
        }
        int left = 0;
        int right = items.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            int midPrice = items[mid][0];
            int compare = Integer.compare(midPrice, query);
            if (compare < 0)
                left = mid + 1;
            else if (compare > 0)
                right = mid - 1;
            else
                return items[mid][1];
        }
        return items[(left + right)/2 ][1];
    }
}        

K?t qu?

K?t qu? có runtime và memory r?t t?t, t?i ?? c?m th?y tho? m?n, h?m nay t?i kh?ng ph?i t?i ?u l?i gi?i thu?t!!!

?? ph?c t?p th?i kh?ng

G?i a là ?? dài c?a m?ng items, b là ?? dài c?a m?ng queries

?? ph?c t?p th?i gian: O(a log(a)) + O(a) + O(b log (a)) = O( (a+b)log(a))

O(a log(a)) là ?? ph?c t?p s?p x?p m?ng items

O(a) là ?? ph?c t?p c?a b??c gán l?i beauty cho t?ng ph?n t?

O(b log (a)) là ?? ph?c t?p khi ph?i l?p qua m?ng queries và tìm ki?m nh? phan

?? ph?c t?p kh?ng gian: O(1) vì t?i ch? ch?a m?t vài bi?n t?m.

K?t lu?n

T?i ngh? m?u ch?t ? ?ay chính làb??c gán l?i beauty cho t?ng ph?n t?. ?i?u này khi?n cho vi?c tìm ki?m nh? phan tr? nên d? dàng h?n r?t nhi?u.

?ay là m?t bài r?t hay (hay thì th??ng khó), nh?ng c?ng may là t?i ?? làm ???c!!!