ในปัญหานี้ เราได้รับเมทริกซ์ไบนารีที่องค์ประกอบของแต่ละแถวถูกจัดเรียงแล้ว ภารกิจของเราคือ หาแถวที่มีจำนวน 1 มากที่สุด
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
mat[][] = {{ 0 1 1 1} {1 1 1 1} {0 0 0 1} {0 0 1 1}}
เอาต์พุต
1
คำอธิบาย
จำนวน 1 ในแต่ละแถวของเมทริกซ์ : แถว 0 : 3 แถว 1 : 4 แถว 2 : 1 แถว 3 : 2
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการหาแถวที่มีดัชนีของ 1 แรกที่น้อยที่สุด
วิธีหนึ่งคือการเดินทางแถวต่อแถวเพื่อหาดัชนีของ 1 แรกซึ่งจะคืนค่าจำนวน 1 สูงสุดในแถว แล้วเราจะคืนค่าแถวที่มี 1 มากที่สุด
อีกวิธีหนึ่งคือการใช้ binary search เพื่อหาการเกิดของ 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
