資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用C++使中位數等於x的最小元素個數。
問題陳述
給定一個大小為n的陣列“arr”和元素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
更新於：2019年10月31日
瀏覽量：181
廣告