資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究使用 C++ 查詢包含最大 1 數的
在此問題中，我們得到一個二進位制矩陣，其中每一行的元素都是經過排序的。我們的任務是找到包含最多 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 計數的行。
另一種方法是使用二分查詢在每一行中找到第 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
更新於： 14-Feb-2022
243 次瀏覽
廣告