[STLC++Set] mergeStringArr

Bài tập.

Cho hai dãy arr1 và arr2 thuộc kiểu vetor<string>. Bạn tạo một dãy từ hai dãy trên theo điều kiện sau:

• Kết quả chỉ chứa các chuôi riêng biệt (Không có hai chuỗi nào giống nhau).
• Kết quả chứa các phần tử trong arr1 mà không xuất hiện trong arr2.
• Các phần tử các dãy kết quả được sắp xếp theo thứ tự từ điểm từ nhỏ đến lớn.

Ví dụ:

• Với arr1 = ["dumv", "learncode", "dumv", "io","fpt"]
arr2 = ["learncode", "dumvtech", "fsoft"].
  Thì kết quả sẽ là mergeStringArr(arr1, arr2) = ["dumv", "fpt", "io"]

Lý thuyết.

Để xóa một phần tư trong set ta dùng hàm erase()  (Độ phức tạp O(logN)).

Hàm không có giá trị trả về, tham giá truyền vào có thể là một iterator trỏ đến phần tử cần xóa hoặc một giá trị cụ thể.

Ví dụ:

	//s = [1,2,3,4,5,6,7]
	s.erase(s.begin()); // s = [1,2,3,4,5,6,7]
	s.erase(3); // s = [1,2,4,5,6,7]

Muốn xóa phần tử thử k trong set s ta làm như sau:

	set <int>:: iterator it = s.begin(); // tạo iterator trỏ vào phần tử đầu trong s
	advance(it,2); // it trỏ đến sô thứ 3 trong s.
	s.erase(it);

Ví dụ:

	//s = {1,2,3,4,5}
	set <int>:: iterator it = s.begin();
	advance(it,3);
	s.erase(it);
	//s = {1,2,3,5}

Hướng dẫn.

Tạo set resSet từ các phần từ trong dãy arr1 (mục đích là để xóa các phần từ khác nhau và sắp xếp chúng tăng dần. 

Tiếp theo sẽ duyệt tất cả các phần tử trong arr2, nếu phần tử đó tồn tại trong reSet thì xóa phần tử đó ở trong reSet.

Code mẫu:

std::vector<std::string> mergeStringArr(std::vector<std::string> arr1, std::vector<std::string> arr2)
{
    std::set<std::string> resSet (arr1.begin(), arr1.end());
    for (auto str : arr2)
    {
        auto search = resSet.find(str);
        if (search != resSet.end()) // found
        {
            resSet.erase(search);
        }
    }
    std::vector<std::string> res (resSet.begin(), resSet.end());
    return res;
}