Gặp lỗi ở 1 số testcase trong Day 8 của Hackerrank

Ko phải lỗi mà giải thuật tốn quá nhiều thời gian nên nó ko cho pass đó.

Vậy có cách nào cải thiện không anh, ngoại trừ dùng map ra

Nếu ko muốn dùng map thì chỉ còn cách cải thiện cách search. :?
Vì mình thấy code chậm là do cách search kia

Nếu ko muốn dùng map thì chỉ còn cách cải thiện cách search. :?

Uhm … vậy anh có cách nào làm cái thuật toán search nó nhanh hơn đủ đáp ứng yêu cầu của hackerrank không ?
Chứ em giải thuật hỏng tốt lắm ^^

Nhưng tại sao lại ko dùng map cho lẹ ;_;

Muốn nhanh hơn Linear Search nữa thì tìm hiểu Binary Search.
Nhưng nó yêu cầu mảng phải sắp xếp

một là dùng map
2 là dùng vector< pair<string, string> >
sort lại rồi tìm kiếm nhị phân
về cơ bản cả 2 đều O(QlogN) nhưng 1 thằng code khỏe 1 thằng code mệt

Cảm ơn mọi người nhiều nhé

Binary Search.

Mà cho em hỏi string thì dùng Binary search kiểu gì anh ?
Vì thường Binary search em toàn dùng cho số, bây giờ nó là chuỗi nên thấy hơi lạ

Đã cải thiện sang Linear Search nhưng vẫn không đủ nhanh như hackerrank yêu cầu

int main() {
   int n;
    std::cin >> n;
    std::vector<std::string> arr_name, arr_phone_number;
    for (int i = 0; i < n; ++i) {
        std::string name, phone_number;
        std::cin >> name >> phone_number;
        arr_name.push_back(name);
        arr_phone_number.push_back(phone_number);
    }
    std::string name;
    while (std::cin >> name) {
        arr_name.push_back(name);
        int a;
        bool Check = false;
        for (int i = 0;; ++i) {
            if (name == arr_name.at(i)) {
                a = i;
                break;
            }
        }
        if (a != n) {
            std::cout << arr_name.at(a) << "=" << arr_phone_number.at(a) << std::endl;
        }
        else {
            std::cout << "Not found" << std::endl;
        }
        arr_name.pop_back();
    }    
    return 0;
}

Chắc phải dùng map quá

linear search thi có cải thiện gì đâu??

binary search cho chuỗi thì cũng ko khác gì số, nếu guess < a[mid] thì cho right = mid, ngược lại thì left = mid rồi cứ thế mà tìm…

C++ có hàm tìm binary search sẵn là std::lower_bound với std::upper_bound. Tìm hiểu 2 hàm này rồi xài cũng được.