Làm cách nào để tìm kiếm hiệu quả trong ma trận đã đặt hàng?

Question

Tôi có một số x bởi y ma trận, trong đó mỗi hàng và mỗi cột đều theo thứ tự tăng dần như được đưa ra bên dưới.

1 5 7 9 
4 6 10 15 
8 11 12 19 
14 16 18 21 

Cách tìm kiếm ma trận này cho một số trong O(x+y)?

Tôi được hỏi câu hỏi này cho một cuộc phỏng vấn, nhưng không thể tìm ra cách. Tò mò để biết nếu nó có thể được thực hiện.

Answer 1

Bắt đầu ở phần tử cuối cùng của hàng đầu tiên (góc trên cùng bên phải).
So sánh nó với key. Chúng tôi có 3 trường hợp:

• Nếu chúng bằng nhau, chúng tôi đã hoàn tất.

• Nếu key lớn hơn yếu tố đó sau đó nó có nghĩa key không thể có mặt trong hàng đó để di chuyển tìm kiếm đến các yếu tố dưới nó.

• Nếu key là ít hơn yếu tố đó thì nó có nghĩa là key thể có mặt ở chỗ hàng về phía trái và không thể có mặt trong cột tiếp tục xuống, do đó di chuyển tìm kiếm đến các yếu tố bên trái của nó.

Tiếp tục làm việc đó cho đến khi bạn tìm thấy phần tử hoặc bạn không thể di chuyển thêm (khóa không tồn tại).

Pseudo code:

Let R be number of rows 
Let C be number of columns 

Let i = 0 
Let j = C-1 

found = false 
while(i>=0 && i<R) && (j>=0 && j<C)) 
    if (matrix[i][j] == key) 
     found = true 
     break 
    else if(matrix[i][j] > key) 
     j-- 
    else if(matrix[i][j] < key) 
     i++ 
end-while 

Answer 2

Chia Matrix trong 4 submatrices. Nếu dưới cùng bên phải của một ma trận phụ nhỏ hơn khóa, hãy loại bỏ nó. Nếu phía trên cùng bên trái của ma trận phụ lớn hơn khóa, hãy loại bỏ nó. Lặp lại quy trình tách cho các ma trận phụ còn lại.

[Cập nhật] Đối với một số mã giả (và thảo luận về sự phức tạp), hãy xem câu trả lời của Jeffrey L Whitledge là this question.

Answer 3

// the matrix is like this, from left to right is ascending, and 
// from down to up is ascending, but the second row'start is not always bigger than the first row's end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/ 
// 1 5 7 9 
// 4 6 10 15 
// 8 11 12 19 
// 14 16 18 21 
// time complexity is O(x+y), x is the count of row, and y is the count of column 

public boolean searchMatrix2(int[][] matrix, int target) { 
    int rowCount = matrix.length; 
    if(rowCount == 0) return false; 

    int colCount = matrix[0].length; 
    if(colCount == 0) return false; 

    //first find the target row, needs O(x) 
    int targetRow = 0; 
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) { 
     targetRow++; 
    } 
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y) 
    boolean result = false; 
    for(int i = 0; i < colCount; i ++) { 
     if(matrix[targetRow][i] == target) { 
      result = true; 
      break; 
     } 
    } 
    return result; 
} 

Trên thực tế, chúng ta có thể sử dụng tìm kiếm nhị phân hai lần, tìm hàng mục tiêu bằng cách tìm kiếm nhị phân đầu tiên, sau đó tìm mục tiêu ở hàng bằng cách tìm kiếm nhị phân, vì vậy mức độ phức tạp thời gian là O (LGX) + O (lgy) , là O (lgx + lgy), tốt hơn O (x + y).