c++ 数组的中位数

### C++ 中计算数组中位数的方法 对于单个已排序数组，找到其中位数相对简单。如果数组长度为奇数，则中位数是位于中间位置的元素；如果是偶数，则中位数通常是中间两个数值的平均值。 #### 单一数组中位数求解方法 当处理单一数组 `arr` 时，可以按照如下方式获取其内部存储数据的中位数[^1]： ```cpp double findMedian(vector<int>& arr) { size_t size = arr.size(); sort(arr.begin(), arr.end()); // 对数组进行升序排列 if (size % 2 == 0) { // 如果数组长度为偶数 return (arr[size / 2 - 1] + arr[size / 2]) / 2.0; } else { // 否则，即数组长度为奇数 return arr[size / 2]; } } ``` 此函数首先对传入的向量进行了排序操作，接着判断该序列内元素数量是否能被二整除来决定采用哪种策略去定位最终的结果。 #### 多个有序数组合并后的中位数求解方法 针对题目描述中的特殊情况——给定两个已经按顺序排列好的不同规模的数据集 `nums1` 和 `nums2` ，为了满足时间复杂度的要求 O(log(m+n))，应采取更高效的解决方案而不是简单的线性扫描或先全部合并且重新排序的方式[^2]。 一种有效途径就是利用二分查找的思想，在较短的那个列表里逐步缩小搜索区间直到锁定目标值的位置。具体实现细节涉及到边界条件控制以及索引转换等方面的知识点[^3]。 下面给出一段基于上述思路编写的示范代码片段用于解决此类问题: ```cpp class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(); int n = nums2.size(); if ((m + n) % 2 != 0){ return getKthElement(nums1, nums2, (m + n)/2 + 1); }else{ return (getKthElement(nums1, nums2, (m + n)/2)+getKthElement(nums1, nums2, (m + n)/2 + 1))/2.0; } return 0.0; } private: double getKthElement(const vector<int>& nums1, const vector<int>& nums2,int k){ /* 主要逻辑 */ int index1 = 0,index2 = 0; while(true){ // 边界情况处理 if(index1==nums1.size()){ return nums2[index2+k-1]; } if(index2==nums2.size()){ return nums1[index1+k-1]; } if(k==1){ return min(nums1[index1],nums2[index2]); } // 正常流程 int newIndex1 = min((int)index1 + k/2 - 1,(int)(nums1.size()-1)); int newIndex2 = min((int)index2 + k/2 - 1,(int)(nums2.size()-1)); int pivot1 = nums1[newIndex1]; int pivot2 = nums2[newIndex2]; if(pivot1<=pivot2){ k -= newIndex1-index1+1; index1=newIndex1+1; }else{ k-=newIndex2-index2+1; index2=newIndex2+1; } } } }; ``` 这段程序定义了一个辅助函数 `getKthElement()` 来帮助主函数完成第 K 小元素的选择工作，从而间接实现了寻找两组有序集合间整体分布下的中位数的功能[^4]。