คำชี้แจงปัญหา
ด้วยอาร์เรย์ "arr" ขนาด n และองค์ประกอบ x ภารกิจคือการค้นหาจำนวนองค์ประกอบขั้นต่ำที่จะเพิ่มในอาร์เรย์เพื่อให้ค่ามัธยฐานเท่ากับ x
ค่ามัธยฐานในอาร์เรย์ที่มีความยาว n คือองค์ประกอบที่มีหมายเลขตำแหน่ง (n-1)/2 หลังจากที่เราจัดเรียงองค์ประกอบในลำดับที่ไม่ลดลง ตัวอย่างเช่น ค่ามัธยฐานของอาร์เรย์ด้านล่างคือ 20 −
arr1[] ={10, 20, 30, 40}
ถ้า arr[] ={1, 2, 3} และ x =4 เราต้องบวกตัวเลข 4 ตัว นั่นคือ {4, 5, 5, 5} ในอาร์เรย์เพื่อให้ค่ามัธยฐานเท่ากับ 4
อัลกอริทึม
อัลกอริทึมนั้นง่ายมาก เราต้องบวกเลข x หนึ่งตัวเข้าไปในอาร์เรย์จนค่ามัธยฐานของอาร์เรย์เท่ากับ x
ตัวอย่าง
#include <iostream>
#include <algorithm>
using namespace std;
int minNumbersToBeAdded(int *arr, int n, int x){
sort(arr, arr + n);
int cnt = 0;
while (arr[(n - 1)/2] != x) {
arr[n] = x;
++n;
sort(arr, arr + n);
++cnt;
}
return cnt;
}
int main(){
int arr[20] = {1, 2, 3};
int x = 4;
int n = 3;
cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Minimum numbers to be added = 4
