Trung tâm cá nhân
sách gpt4 ai đã đi

Triển khai C++ của LeetCode (74. Tìm kiếm ma trận hai chiều)

In lại Tác giả:qq735679552 Thời gian cập nhật: 2022-09-27 22:32:09 30 4
mua khóa gpt4 Nike

CFSDN nhấn mạnh vào việc tạo ra giá trị thông qua mã nguồn mở. Chúng tôi cam kết xây dựng một nền tảng chia sẻ tài nguyên để mọi người làm CNTT có thể tìm thấy thế giới tuyệt vời của riêng mình tại đây.

Bài đăng trên blog CFSDN này là bản triển khai C++ của LeetCode (74. Tìm kiếm ma trận 2D) được tác giả thu thập và biên soạn. Nếu bạn quan tâm đến bài viết này, hãy nhớ thích nó.

[LeetCode] 74. Tìm kiếm một Ma trận 2D Tìm kiếm một ma trận 2D

Viết một thuật toán hiệu quả để tìm kiếm một giá trị trong ma trận mxn. Ma trận này có các thuộc tính sau

  • Các số nguyên trong mỗi hàng được sắp xếp từ trái sang phải.
  • Số nguyên đầu tiên của mỗi hàng lớn hơn số nguyên cuối cùng của hàng trước đó.

Ví dụ 1

Triển khai C++ của LeetCode (74. Tìm kiếm ma trận hai chiều)

Đầu vào: ma trận = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], mục tiêu = 3 Đầu ra: đúng.

Ví dụ 2

Triển khai C++ của LeetCode (74. Tìm kiếm ma trận hai chiều)

Đầu vào: ma trận = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], mục tiêu = 13 Đầu ra: sai.

Hạn chế

  • m == chiều dài ma trận
  • n == ma trận[i].chiều dài
  • 1 <= m, n <= 100
  • -104 <= ma trận[i][j], mục tiêu <= 104

Câu hỏi này yêu cầu tìm kiếm ma trận hai chiều. Vì ma trận đã cho có thứ tự nên việc sử dụng tìm kiếm nhị phân là điều tự nhiên. Bạn có thể sử dụng tìm kiếm nhị phân trên cột đầu tiên để tìm vị trí của hàng có giá trị mục tiêu, sau đó sử dụng tìm kiếm nhị phân trên hàng để tìm giá trị mục tiêu có tồn tại hay không. Đối với tìm kiếm nhị phân đầu tiên, vì có thể không có giá trị mục tiêu nào trong các số ở cột đầu tiên, làm thế nào để tìm kiếm? Nếu bạn đang tìm kiếm số đầu tiên không nhỏ hơn giá trị mục tiêu, khi mục tiêu ở cột đầu tiên, hàng mà mục tiêu nằm sẽ được trả về, nhưng nếu mục tiêu không ở đó, nó có thể trả về hàng tiếp theo, rất khó để thống nhất. Vì vậy, bạn có thể tìm thấy số đầu tiên lớn hơn giá trị mục tiêu, đó là danh mục thứ ba trong bài tóm tắt. Theo cách này, miễn là bạn quay lại một, thì đó phải là hàng mà mục tiêu nằm. Nhưng một điều cần lưu ý là nếu giá trị trả về là 0, bạn không thể quay lại để tránh vượt qua ranh giới. Hãy nhớ đưa ra phán đoán. Sau khi tìm được số hàng nơi mục tiêu nằm, bạn có thể sử dụng tìm kiếm nhị phân một lần nữa. Đây là danh mục đầu tiên trong bài tóm tắt, tìm số có cùng giá trị với mục tiêu. Đây cũng là danh mục đơn giản nhất và có thể thực hiện trong vài phút. Xem mã bên dưới:

Giải pháp 1:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
hai mươi mốt
hai mươi hai
hai mươi ba
lớp học Giải pháp {
công cộng :
     bool searchMatrix(vector<> số nguyên >>& ma trận, số nguyên mục tiêu) {
         nếu như (ma trận.empty() || matrix[0].empty()) trở lại SAI ;
         số nguyên trái = 0, phải = kích thước ma trận();
         trong khi (trái < phải) {
             số nguyên giữa = (trái + phải) / 2;
             nếu như (ma trận[giữa][0] == mục tiêu) trở lại ĐÚNG VẬY ;
             nếu như (ma trận[giữa][0] < mục tiêu) bên trái = giữa + 1;
             khác phải = giữa;
         }
         số nguyên tmp = (phải > 0) ? (phải - 1) : phải;
         trái = 0;
         phải = ma trận[tmp].kích thước();
         trong khi (trái < phải) {
             số nguyên giữa = (trái + phải) / 2;
             nếu như (ma trận[tmp][mid] == mục tiêu) trở lại ĐÚNG VẬY ;
             nếu như (ma trận[tmp][mid] < mục tiêu) trái = giữa + 1;
             khác phải = giữa;
         }
         trở lại SAI ;
     }
};

Tất nhiên, vấn đề này cũng có thể được giải quyết bằng cách sử dụng tìm kiếm nhị phân. Nếu chúng ta duyệt mảng hai chiều theo cách hình chữ S, chúng ta có thể nhận được một mảng một chiều có thứ tự. Chúng ta chỉ cần sử dụng tìm kiếm nhị phân một lần. Chìa khóa nằm ở việc chuyển đổi tọa độ. Cách chuyển đổi tọa độ hai chiều và tọa độ một chiều là điểm chính. Sau khi chuyển đổi một mảng một chiều có độ dài n thành một mảng hai chiều có m * n (m * n = n), phần tử có chỉ số i trong mảng một chiều ban đầu sẽ xuất hiện ở vị trí [i / n ][ i% n ] trong mảng hai chiều. Với điều này, mã rất dễ viết:

Giải pháp 2:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
lớp học Giải pháp {
công cộng :
     bool searchMatrix(vector<> số nguyên >>& ma trận, số nguyên mục tiêu) {
         nếu như (ma trận.empty() || matrix[0].empty()) trở lại SAI ;
         số nguyên m = matrix.size(), n = matrix[0].size();
         số nguyên trái = 0, phải = m * n;
         trong khi (trái < phải) {
             số nguyên giữa = (trái + phải) / 2;
             nếu như (ma trận[giữa / n][giữa % n] == mục tiêu) trở lại ĐÚNG VẬY ;
             nếu như (ma trận[giữa / n][giữa % n] < mục tiêu) bên trái = giữa + 1;
             khác phải = giữa;
         }
         trở lại SAI ;
     }
};

Trên thực tế, bài toán này không yêu cầu tìm kiếm nhị phân. Cũng có thể sử dụng trực tiếp con trỏ double, với i trỏ đến 0 và j trỏ đến số cột. Theo cách này, số đầu tiên được xác minh là số ở góc trên bên phải của mảng hai chiều. Nếu số này bằng với mục tiêu, thì true được trả về trực tiếp; nếu lớn hơn mục tiêu, thì có nghĩa là cần phải giảm số đó, và số cột j được giảm đi 1; nếu nhỏ hơn mục tiêu, thì có nghĩa là cần phải tăng số đó, và số hàng i được tăng lên 1. Nếu vòng lặp while thoát và mục tiêu vẫn không được tìm thấy, chỉ cần trả về false. Xem mã bên dưới:

Giải pháp 3:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
lớp học Giải pháp {
công cộng :
     bool searchMatrix(vector<> số nguyên >>& ma trận, số nguyên mục tiêu) {
         nếu như (ma trận.empty() || matrix[0].empty()) trở lại SAI ;
         số nguyên tôi = 0, j = ( số nguyên )matrix[0].size() - 1;
         trong khi (i < kích thước ma trận() && j >= 0) {
             nếu như (ma trận[i][j] == mục tiêu) trở lại ĐÚNG VẬY ;
             khác nếu như (ma trận[i][j] > mục tiêu) --j;
             khác ++tôi;
         }  
         trở lại SAI ;
     }
};

Đây là phần cuối của bài viết này về việc triển khai LeetCode (74. Tìm kiếm ma trận 2D) trong C++. Để biết thêm thông tin về việc triển khai tìm kiếm ma trận 2D trong C++, vui lòng tìm kiếm các bài viết trước đây của tôi hoặc tiếp tục duyệt các bài viết liên quan sau. Tôi hy vọng bạn sẽ ủng hộ tôi trong tương lai! .

Liên kết gốc: https://www.cnblogs.com/grandyang/p/4323301.html.

Cuối cùng, bài viết này về việc triển khai LeetCode (74. Tìm kiếm ma trận hai chiều) bằng C++ ở đây. Nếu bạn muốn biết thêm về việc triển khai LeetCode (74. Tìm kiếm ma trận hai chiều bằng C++), vui lòng tìm kiếm các bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .

30 4 0
Bài viết được đề xuất: Một cuộc thảo luận ngắn gọn về chức năng điều chỉnh JavaScript và chống rung
Bài viết được đề xuất: Giới thiệu về các hàm chuyển đổi đối tượng toString() và valueOf() trong JavaScript
Bài viết được đề xuất: JS triển khai hiệu ứng kéo hộp mờ
Bài viết được đề xuất: Giới thiệu về các quy tắc chuyển đổi đối tượng thành số hoặc chuỗi trong JavaScript
qq735679552
Hồ sơ cá nhân

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá Didi Taxi miễn phí
Mã giảm giá Didi Taxi
Các bài viết nóng hổi trên toàn bộ trang web
Giấy chứng nhận ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com