Trong bài toán này, chúng ta được cung cấp một ma trận nhị phân, trong đó mỗi hàng được sắp xếp. Nhiệm vụ của chúng ta là Tìm số hàng của ma trận nhị phân có số lượng lớn nhất là 1.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
binMat[][] = {
1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 1
} Đầu ra
1
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là đếm tổng số 1 trong mỗi hàng. Và sau đó trả về số hàng với số lượng tối đa 1.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
int oneCount = 0;
for(int j = 0; j < C; j++){
if(mat[i][j])
oneCount++;
}
if(oneCount > max1Count){
max1Count = oneCount;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} Đầu ra
Số hàng với số lượng lớn nhất của 1 là 1 Một giải pháp tốt hơn cho vấn đề có thể là sử dụng tìm kiếm nhị phân trên mỗi hàng để tìm lần xuất hiện đầu tiên của 1 trong hàng. Số 1 trong hàng có thể được tìm thấy bằng cách sử dụng kích thước hàng - chỉ số của số 1. Sử dụng điều này, chúng tôi có thể tìm số 1 trong mỗi hàng và sau đó quay lại hàng có số 1 tối đa
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
index = binarySearch1Row(mat[i], 0, C-1);
if (index != -1 && ( C-index) > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} Đầu ra
The number of row with maximum number of 1's is 1
Một tối ưu hóa được thêm vào phương pháp trên có thể kiểm tra xem hàng hiện tại có nhiều số 1 hay không thì hàng trước đó sử dụng chỉ mục của số 1 đầu tiên. Nếu nó có nhiều số 1 thì thực hiện tìm kiếm nhị phân nhưng từ 0 đến chỉ mục của số 1 đầu tiên ở hàng cuối cùng.
Điều này sẽ giúp tiết kiệm chi phí tính toán số 1 liên tiếp với ít hơn 1 so với hiện tại.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int i, index;
int max1Row = 0;
int max1Count = binarySearch1Row(mat[0], 0, C - 1);
for (i = 1; i < R; i++){
if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) {
index = binarySearch1Row (mat[i], 0, C - max1Count);
if (index != -1 && C - index > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
else
max1Count = binarySearch1Row(mat[i], 0, C - 1);
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} Đầu ra
The number of row with maximum number of 1's is 1