[Cpp-STL] Set4

Bài tập.

Cho một dãy gồm các số nguyên và một số nguyên k.

Hãy kiểm tra xem trong dãy đó có phần tử giá trị k hay không, trả về true nếu có, false nếu không.

Ví dụ:

• Với arr = [1, 2, 5, 3] và  k = 5 thì setFind(arr, k) = true.
  
  
• Với arr = [4, 6, 2, 7] và k = 3 thì setFind(arr, k) = false.

Lý thuyết.

Để kiểm tra một giá trị có tồn tại trong một set hay không, ta sẽ dùng hàm find() (Độ phức tạp O(logN)).

Hàm s.find(x) sẽ trả về iterator trỏ đến phần tử mang giá trị x trong set s, nếu không tồn tại giá trị x trong s thì hàm sẽ trả về s.end().

Ví dụ:

	set <int>:: iterator it = s.find(x); // lấy con trỏ đang trỏ đến số có giá rị x
	if (it == s.end()){ // nếu không tồn tại giá trị x trong set s
		...
	}else{ // có tồn tại giá trị x trong set s
		...
	}

Hướng dẫn.

Code mẫu:

bool setFind(std::vector<int> arr, int k)
{
    std::set<int> s(arr.begin(), arr.end());
    std::set<int>:: iterator it = s.find(k);
    return it != s.end();
}