ในปัญหานี้ เราได้รับ 2D array 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. แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการจัดเก็บองค์ประกอบทั้งหมดของอาร์เรย์ จากนั้นค้นหาองค์ประกอบมัธยฐานโดยการจัดเรียงอาร์เรย์
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการค้นหาองค์ประกอบมัธยฐานโดยใช้ข้อเท็จจริงที่ is มีองค์ประกอบที่เล็กกว่า (r*c)/2 ในเมทริกซ์ และเราจะพบองค์ประกอบในอาร์เรย์ที่เป็นไปตามเงื่อนไขนี้ สำหรับสิ่งนี้ เราจะใช้การค้นหาแบบไบนารีบนเมทริกซ์โดยใช้องค์ประกอบที่เล็กที่สุดและใหญ่ที่สุดของเมทริกซ์ จากนั้นเราจะหาค่ากลางของช่วงและตรวจสอบจำนวนองค์ประกอบที่เล็กกว่าในนั้น ถ้ามันเท่ากับ r*c/2 ให้ส่งคืนตัวเลข ถ้ามันมากกว่า (r*c)/2 เราจะเปลี่ยนองค์ประกอบที่ใหญ่ที่สุดเป็นองค์ประกอบที่เล็กกว่าตรงกลางที่พบ และทำเช่นเดียวกันกับส่วนที่เล็กที่สุดหากจำนวนนั้นน้อยกว่า (r*c)/2
การนับองค์ประกอบที่เล็กกว่าองค์ประกอบตรงกลาง เราสามารถนับองค์ประกอบทั้งหมดตามลำดับโดยการค้นหาดัชนีขององค์ประกอบแรกมากกว่าตรงกลางหรือเพียงแค่ใช้ upper_bound ซึ่งเป็นฟังก์ชัน inbuilt ใน c++
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
