ในปัญหานี้ เราได้รับสตรีมข้อมูลที่อ่านจำนวนเต็มอย่างต่อเนื่อง งานของเราคือสร้างโปรแกรมที่จะอ่านองค์ประกอบและคำนวณค่ามัธยฐานสำหรับองค์ประกอบเหล่านี้
ค่ามัธยฐาน ของอาร์เรย์เป็นองค์ประกอบตรงกลางจากลำดับการเรียงลำดับ (สามารถขึ้นหรือลงได้)
คำนวณค่ามัธยฐาน
สำหรับการนับคี่ ค่ามัธยฐานคือองค์ประกอบตรงกลาง
สำหรับการนับคู่ ค่ามัธยฐานคือค่าเฉลี่ยขององค์ประกอบกลางสองตัว
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − 3, 65, 12, 20, 1
ในแต่ละอินพุต
Input - 3 : sequence -(3) : median - 3 Input - 65 : sequence -(3, 65) : median - 34 Input - 12 : sequence -(3, 12, 65) : median - 12 Input - 20 : sequence -(3, 12, 20, 65) : median - 16 Input - 1 : sequence -(1, 3, 12, 20, 65) : median - 12
เราใช้การเรียงลำดับที่นี่เพื่อให้การคำนวณค่ามัธยฐานง่ายขึ้น
ในการแก้ปัญหานี้ เรามีวิธีแก้ปัญหาหลายอย่างที่ใช้การเรียงลำดับในแต่ละขั้นตอน จากนั้นหาค่ามัธยฐาน สร้าง BST ที่สมดุลในตัวเอง หรือใช้ฮีป ฮีปน่าจะเป็นวิธีแก้ปัญหาที่ดีที่สุดในการหาค่ามัธยฐาน max-heap หรือ min-heap สามารถให้ค่ามัธยฐานในการแทรกทุกครั้งและเป็นวิธีแก้ปัญหาที่มีประสิทธิภาพเช่นกัน
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <iostream>
using namespace std;
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
bool Greater(int a, int b){
return a > b;
}
bool Smaller(int a, int b){
return a < b;
}
int Signum(int a, int b){
if( a == b )
return 0;
return a < b ? -1 : 1;
}
class Heap{
public:
Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)
{ heapSize = -1; }
virtual bool Insert(int e) = 0;
virtual int GetTop() = 0;
virtual int ExtractTop() = 0;
virtual int GetCount() = 0;
protected:
int left(int i) {
return 2 * i + 1;
}
int right(int i) {
return 2 * (i + 1);
}
int parent(int i) {
if( i <= 0 ){
return -1;
}
return (i - 1)/2;
}
int *A;
bool (*comp)(int, int);
int heapSize;
int top(void){
int max = -1;
if( heapSize >= 0 )
max = A[0];
return max;
}
int count() {
return heapSize + 1;
}
void heapify(int i){
int p = parent(i);
if( p >= 0 && comp(A[i], A[p]) ) {
swap(A[i], A[p]);
heapify(p);
}
}
int deleteTop(){
int del = -1;
if( heapSize > -1){
del = A[0];
swap(A[0], A[heapSize]);
heapSize--;
heapify(parent(heapSize+1));
}
return del;
}
bool insertHelper(int key){
bool ret = false;
if( heapSize < MAX_HEAP_SIZE ){
ret = true;
heapSize++;
A[heapSize] = key;
heapify(heapSize);
}
return ret;
}
};
class MaxHeap : public Heap {
private:
public:
MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }
int GetTop() {
return top();
}
int ExtractTop() {
return deleteTop();
}
int GetCount() {
return count();
}
bool Insert(int key) {
return insertHelper(key);
}
};
class MinHeap : public Heap{
private:
public:
MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { }
int GetTop() {
return top();
}
int ExtractTop() {
return deleteTop();
}
int GetCount() {
return count();
}
bool Insert(int key) {
return insertHelper(key);
}
};
int findMedian(int e, int &median, Heap &left, Heap &right){
switch(Signum(left.GetCount(), right.GetCount())){
case 0: if( e < median ) {
left.Insert(e);
median = left.GetTop();
}
else{
right.Insert(e);
median = right.GetTop();
}
break;
case 1: if( e < median ){
right.Insert(left.ExtractTop());
left.Insert(e);
}
else
right.Insert(e);
median = ((left.GetTop()+right.GetTop())/2);
break;
case -1: if( e < median )
left.Insert(e);
else {
left.Insert(right.ExtractTop());
right.Insert(e);
}
median = ((left.GetTop()+right.GetTop())/2);
break;
}
return median;
}
void printMedianStream(int A[], int size){
int median = 0;
Heap *left = new MaxHeap();
Heap *right = new MinHeap();
for(int i = 0; i < size; i++) {
median = findMedian(A[i], median, *left, *right);
cout<<"Median of elements : ";
for(int j = 0; j<=i;j++) cout<<A[j]<<" ";
cout<<"is "<<median<<endl;
}
}
int main(){
int A[] = {12, 54, 9, 6, 1};
int size = ARRAY_SIZE(A);
printMedianStream(A, size);
return 0;
} ผลลัพธ์
Median of elements : 12 is 12 Median of elements : 12 54 is 33 Median of elements : 12 54 9 is 12 Median of elements : 12 54 9 6 is 10 Median of elements : 12 54 9 6 1 is 9
