資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中查詢行排序矩陣的中位數
在這個問題中，我們得到一個二維陣列mat[r][c]，其元素按行排序。我們的任務是在行排序矩陣中查詢中位數。
描述 - 我們需要找到矩陣元素的中位數。
讓我們舉個例子來理解這個問題：
輸入
mat = {
{2, 4, 7},
{5, 6, 8},
{4, 8, 9}
}輸出
6
解釋
儲存在陣列中的矩陣元素為：
{2, 4, 4, 5, 6, 7, 8, 8, 9}
The median is 6.解決方案方法
解決這個問題的一個簡單方法是儲存陣列的所有元素。然後透過對陣列排序來找到中位數元素。
解決這個問題的一個更有效的方法是利用矩陣中恰好有(r*c)/2個較小元素這一事實來查詢中位數元素。我們將找到滿足此條件的陣列中的元素。為此，我們將對矩陣進行二分查詢，取矩陣的最小和最大元素，然後找到範圍的中點，並檢查其中較小元素的數量。如果它等於r*c/2，則返回該數字。如果它大於(r*c)/2，那麼我們將最大元素更改為小於找到的中點的元素，如果計數小於(r*c)/2，則對最小元素執行相同的操作。
小於中間元素的元素的數量，我們可以透過查詢大於中間元素的第一個元素的索引來逐行計數所有元素，或者簡單地使用c++中的內建函式upper_bound。
程式說明了我們解決方案的工作原理：
示例
#include<bits/stdc++.h>
using namespace std;
#define c 3
#define r 3
int findMedian(int mat[][c]) {
int smallest = INT_MAX, largest = INT_MIN;
for (int i=0; i<r; i++) {
if (mat[i][0] < smallest)
smallest = mat[i][0];
if (mat[i][c-1] > largest)
largest = mat[i][c-1];
}
while (smallest < largest){
int mid = smallest + (largest - smallest) / 2;
int smallCount = 0;
for (int i = 0; i < r; ++i)
smallCount += upper_bound(mat[i], mat[i]+c, mid) -
mat[i];
if (smallCount < ( (r * c + 1) / 2 ))
smallest = mid + 1;
else
largest = mid;
}
return smallest;
}
int main(){
int mat[][c]= { {2, 5, 7}, {4, 6, 8}, {1, 8, 9} };
cout<<"The median of the matrix is "<<findMedian(mat);
return 0;
}輸出
The median of the matrix is 6
更新於：2021年3月12日
212 次瀏覽
廣告