ในปัญหานี้ เราได้รับเมทริกซ์ไบนารีซึ่งแต่ละแถวจะถูกจัดเรียง งานของเราคือค้นหาหมายเลขแถวของเมทริกซ์ไบนารีที่มีจำนวนสูงสุด 1 วินาที
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
binMat[][] = {
1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 1
} ผลลัพธ์
1
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการนับจำนวนรวมของ 1 ในแต่ละแถว แล้วส่งคืนหมายเลขแถวโดยมีจำนวนสูงสุด 1 ครั้ง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
จำนวนแถวที่มีจำนวนสูงสุด 1 คือ 1 วิธีแก้ไขปัญหาที่ดีกว่าคือการใช้การค้นหาแบบไบนารีในแต่ละแถวเพื่อค้นหาการเกิดขึ้นครั้งแรกของ 1 ในแถว ตัวเลข 1 ในแถวสามารถพบได้โดยใช้ขนาดแถว - ดัชนีของ 1 แรก เมื่อใช้สิ่งนี้ เราจะสามารถหาจำนวน 1 ในแต่ละแถวแล้วส่งคืนแถวที่มีจำนวนสูงสุด 1
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The number of row with maximum number of 1's is 1
การปรับให้เหมาะสมที่เพิ่มไปยังวิธีการข้างต้นสามารถตรวจสอบว่าแถวปัจจุบันมีมากกว่า 1 ตัวแล้วหรือยังแถวก่อนหน้าโดยใช้ดัชนีของ 1 ตัวแรก หากมีมากกว่า 1 ตัว ให้ทำการค้นหาแบบไบนารี แต่จาก 0 ถึงดัชนีของ 1 แรกในแถวสุดท้าย
วิธีนี้จะช่วยประหยัดค่าใช้จ่ายในการคำนวณจำนวน 1 ในแถวที่มี 1 น้อยกว่าปัจจุบัน
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The number of row with maximum number of 1's is 1
