ในปัญหานี้ เราได้รับเมทริกซ์ไบนารีที่องค์ประกอบของแต่ละแถวจะถูกจัดเรียง งานของเราคือ ค้นหาแถวที่มีจำนวนสูงสุด 1 วินาที .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
mat[][] = {{ 0 1 1 1}
{1 1 1 1}
{0 0 0 1}
{0 0 1 1}} ผลผลิต
1
คำอธิบาย
The count of 1’s in each row of the matrix : Row 0 : 3 Row 1 : 4 Row 2 : 1 Row 3 : 2
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการหาแถวที่มีดัชนีที่เล็กที่สุดของ 1 ตัวแรก
วิธีหนึ่งคือการใช้การข้ามแถวอย่างชาญฉลาดเพื่อค้นหาดัชนีของ 1 ตัวแรกซึ่งจะคืนค่าจำนวนสูงสุดของ 1 ในแถว จากนั้นเราจะส่งคืนแถวโดยมีจำนวนสูงสุด 1 ครั้ง
อีกวิธีหนึ่งคือการใช้ การค้นหาไบนารี เพื่อหาการเกิดขึ้นของ 1 ตัวแรกในแต่ละแถว จากนั้นเราจะคืนค่าสูงสุด 1
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findFirst1BinSearch(bool arr[], int low, int high){
if(high >= low){
int mid = low + (high - low)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return findFirst1BinSearch(arr, (mid + 1), high);
else
return findFirst1BinSearch(arr, low, (mid -1));
}
return -1;
}
int findMaxOneRow(bool mat[R][C]){
int max1RowIndex = 0, max = -1;
for (int i = 0; i < R; i++){
int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
if (first1Index != -1 && C-first1Index > max){
max = C - first1Index;
max1RowIndex = i;
}
}
return max1RowIndex;
}
int main(){
bool mat[R][C] = { {0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1}};
cout<<"The row with maximum number of 1's in the matrix is "<<findMaxOneRow(mat);
return 0;
} ผลลัพธ์
The row with maximum number of 1's in the matrix is 1
