[Cpp-STL] Set5

Bài tập.

Cho một dãy số nguyên arr và số nguyên k.

Hãy tìm ra hai số:

• Số m là số nhỏ nhất trong dãy lớn hơn k. Nếu không có thì m = -1.
• Số n là số nhỏ nhất trong dãy lớn hơn hoặc bằng k. Nếu không có thì n = -1.

Kết quả trả về là dãy gồm 2 số [m,n].

Ví dụ:

• Với arr = [1, 2, 3, 4, 5] và k = 4 thì setFunction(a, k) = [5,4].
• Với arr = [1, 2, 3] và k = 3 thì setFunction(a, k) = [-1,3].

Lý thuyết.

Trong bài này chúng ta sẽ tìm hiểu về hai hàm:

• upper_bound() :  Trả về iterator đến vị trí phần tử nhỏ nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN). 
• lower_bound() : Trả về iterator đến vị trí phần tử nhỏ nhất mà không nhỏ hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).

Ví dụ:

	// s = {1,2,3,4,5}
	set <int>:: iterator it = s.lower_bound(4);
	if (it == s.end()){
		cout << -1;
	}else{
		cout << *it;
	}
	//Kết quả sẽ là 4

	it = s.upper_bound(4);
	if (it == s.end()){
		cout << -1;
	}else{
		cout << *it;
	}
	//Kết quả sẽ là 5

Hướng dẫn.

Code mẫu:

std::vector<int> setFunction(std::vector<int> arr, int k)
{
    int m,n;
    std::set<int> s(arr.begin(), arr.end());
    set <int>:: iterator it;

    it = s.upper_bound(k);
    m =  (it != s.end()) ? *it : -1;

    it = s.lower_bound(k);
    n = (it != s.end()) ? *it : -1;

    return {m,n};
}