Bài viết gồm 3 phần:

• Giới thiệu qua về cấu trúc dữ liệu giải thuật.
• Giải thích mục đích của series giải thuật cơ bản - mỗi tháng một challenge.
• Challenge 2020/09.

1/ Giới thiệu:

• Cấu trúc dữ liệu và giải thuật (CTDL-GT) là kiến thức quan trọng đối với một Software Engineer.
• Việc hiểu và sử dụng CTDL-GT sẽ giúp bạn viết code logic hơn, giải quyết vấn đề tốt hơn.
• Kiến thức về CTDL-GT hiện tại không phải là trending cũng như không nhìn thấy hiệu quả tức khắc như công nghệ mới: framework hay ngôn ngữ mới. Tuy nhiên, nếu bạn muốn trở thành một Software Engineer chuyên nghiệp, bạn cần hiểu và sử dụng thành thạo CTDL-GT.

2/ Mục đích:

• Series về giải thuật cơ bản là để recap lại kiến thức về CTDL-GT thông qua các vấn đề thực tế, thay vì lý thuyết nhàm chán. Đồng nghĩa với việc, bạn cần chủ động tìm đọc về các kiến thức CTDL-GT liên quan tới các vấn đề đó.
• Cách thức hoạt động: Mỗi tháng, chọn ra một vài vấn đề để mọi người cùng suy nghĩ và giải quyết.
• Quá trình đọc hiểu/phân tích/giải quyết này sẽ giúp bạn nâng cao khả năng phân tích yêu cầu bài toán, tìm ra giải pháp cũng như khả năng lựa chọn hướng giải quyết khi xử lý vấn đề.
• Mỗi vấn đề đều được đính kèm lời giải tương ứng, tuy nhiên, bạn nên tự phân tích, giải quyết, thử-và-sai trước khi xem lời giải thì sẽ có hiệu quả nhiều hơn.

3/ Challenge 2020/09:

• Link: https://leetcode.com/problems/search-a-2d-matrix-ii/

Tóm tắt:

Viết một thuật toán để tìm kiếm một giá trị target trong một ma trận m x n. Ma trận có 2 đặc điểm:

• các số trên mỗi hàng đã được sắp xếp tăng dần từ trái qua phải.
• các số trên mỗi cột đã được sắp xếp tăng dần từ trên xuống dưới.

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Ví dụ, ở ma trận trên:

• nếu input là 5 thì kết quả trả về là true
• nếu input là 20 thì kết quả trả về là false

Một số kiến thức liên quan:

• phân tích độ phức tạp thuật toán
• sắp xếp
• tìm kiếm nhị phân

Tạm dừng màn hình ở đây và suy nghĩ xem sao bạn nhé.

Lời giải

Solution 1: Lời giải cơ bản

• ý tưởng: bạn duyệt từng hàng, kiểm tra tại hàng đó xem có giá trị cần tìm hay không. nếu có trả về true. Khi bạn duyệt tới hết ma trận m x n mà vẫn chưa tìm được giá trị cần tìm, thì trả về false
• độ phức tạp thuật toán: vì bạn phải duyệt qua từng hàng (m), và mỗi hàng duyệt qua từng cột (n) nên độ phức tạp thuật toán về mặt thời gian sẽ là O(m x n)
• source code C++

     bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows == 0) return false;
        int columns = matrix[0].size();
        
        for(int r = 0; r < rows; r++) {
            for (int c = 0; c < columns; c++) {
                if (matrix[r][c] == target) {
                    return true;
                }
            }
        }
        
        return false;
    }

Solution 2: Lời giải tốt hơn

• ý tưởng: vì mỗi hàng đã được sắp xếp theo chiều tăng dần rồi, bạn có thể duyệt từng hàng, và áp dụng tìm kiếm nhị phân để kiểm tra trong hàng đó có chứa giá trị cần tìm hay không.

• độ phức tạp thuật toán: vì bạn phải duyệt từng hàng m và với mỗi hàng, bạn áp dụng tìm kiếm nhịn phân log(n) nên độ phức tạp thuật toán theo thời gian sẽ là O(mlog(n)

• source code C++:

    bool binarySearch(vector<int>& array, int c, int max_c, int target) 
    {
        while(c <= max_c) {
            int mid = c + (max_c - c) / 2;
            if (array[mid] == target) {
                return true;
            }
            if (array[mid] > target) {
                max_c = mid - 1;
            } 
            else {
                c = mid + 1;
            }
        }

        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        int rows = matrix.size();
        if (rows == 0) return false;
        int columns = matrix[0].size();
        
        for(int r = 0; r < rows; r++) {
            int c = 0, max_c = columns - 1;
            if (binarySearch(matrix[r], c, max_c, target)) {
                return true;
            }
        }
        return false;
    }

Solution 3: Lời giải tốt nhất

• ý tưởng: ở bài tập này, để tìm xem giá trị target trong ma trận m x n hay không, thì cần tìm xem có tồn tại 1 vị trí [i,j] mà tại đó matrix[i][j] == target

  • i, j thay đổi theo hàng và cột. Và ma trận này đã được sắp xếp tăng dần từ trái qua phải, từ trên xuống dưới rồi, nên nếu ta có thể cố định i hoặc j để tìm vị trí tiếp theo của [i, j] và kiểm tra với target, thì có thể giảm được số lượng vị trí [i,j] cần duyệt.
  • nhận xét: tại 1 vị trí [i, j],
    • nếu matrix[i][j] > target thì target nếu tồn tại trong ma trận m*n thì sẽ chỉ nằm từ cột 0 -> j-1.
    • nếu matrix[i][j] < target thì target nếu tồn tại trong ma trận m*n thì sẽ chỉ nằm từ hàng i -> max row.
    • nếy matrix[i][j] == target, return true
  • như vậy, ta có thể bắt đầu từ từ vị trí i = 0, j = max_column thì có thể giảm số lượng duyệt i, j không cần thiết.

• độ phức tạp thuật toán theo thời gian là O(m + n)

• source code C++:

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows == 0) return false;
        int columns = matrix[0].size();

        int r = 0, c = columns - 1;
        while (r < rows && c >= 0) {
            if (matrix[r][c] == target) {
                return true;
            }
            if (matrix[r][c] > target) {
                c--;
            }
            else {
                r++;
            }
        }
        
        return false;
    }

Hi vọng bạn tìm được một cái gì đó mới thông qua bài viết này. Mọi thắc mắc, hoặc có sự nhầm lẫn ở bài viết, mong các bạn nhiệt tình comment ạ.

Happy coding!!!