Trong bài toán này, chúng ta được đưa ra một mat mảng 2D [r] [c] có các phần tử được sắp xếp theo thứ tự. Nhiệm vụ của chúng ta là Tìm giá trị trung bình trong một ma trận được sắp xếp theo hàng.
Mô tả - chúng ta cần tìm trung vị của các phần tử của ma trận.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
mat = {
{2, 4, 7},
{5, 6, 8},
{4, 8, 9}
} Đầu ra
6
Giải thích
Các phần tử của ma trận được lưu trữ trong mảng là &trừ
{2, 4, 4, 5, 6, 7, 8, 8, 9}
The median is 6. Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là lưu trữ tất cả các phần tử của mảng. Sau đó tìm phần tử trung vị bằng cách sắp xếp mảng.
Một giải pháp hiệu quả hơn cho vấn đề là tìm phần tử trung vị bằng cách sử dụng thực tế là có chính xác (r * c) / 2 phần tử nhỏ hơn trong ma trận. Và chúng ta sẽ tìm phần tử trong mảng tuân theo điều kiện này. Đối với điều này, chúng tôi sẽ sử dụng tìm kiếm nhị phân trên ma trận lấy phần tử nhỏ nhất và lớn nhất của ma trận và sau đó chúng tôi sẽ tìm giữa phạm vi và kiểm tra số lượng phần tử nhỏ hơn trong đó. Nếu nó bằng r * c / 2 thì trả về số. Nếu nó lớn hơn (r * c) / 2, thì chúng ta sẽ đổi phần tử lớn nhất thành phần tử nhỏ hơn ở giữa vừa tìm được và thực hiện tương tự với phần tử nhỏ nhất nếu số đếm nhỏ hơn (r * c) / 2.
Số lượng các phần tử nhỏ hơn phần tử giữa, chúng ta có thể đếm tất cả các phần tử theo hàng bằng cách tìm chỉ số của phần tử đầu tiên lớn hơn giữa hoặc chỉ cần sử dụng upper_bound là một hàm có sẵn trong c ++.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The median of the matrix is 6