C++求求无序数组的中位数，当数组个数为偶数时，返回中间两个数中较大的一个数

在C++中，计算无序数组的中位数是一个常见的问题。当数组元素个数为偶数时，确实需要找到中间两个数并返回较大的那个作为中位数。下面是一种简单的解决方案： 1. 首先，你需要对数组进行排序。你可以使用标准库中的`std::sort`函数，它会将数组元素从小到大排列。 ```cpp #include <algorithm> #include <vector> // 假设你的数组叫arr，长度为size std::vector<int> arr = {...}; // 无序数组 int size = arr.size(); std::sort(arr.begin(), arr.end()); ``` 2. 排序后，由于数组长度是偶数，中位数位于中间两个位置。你可以通过索引来访问这两个元素，并返回较大的一个。 ```cpp if (size % 2 == 0) { int mid1 = arr[size / 2 - 1]; int mid2 = arr[size / 2]; return std::max(mid1, mid2); } else { // 如果数组长度是奇数，直接返回中间的那个元素 return arr[size / 2]; } ```

### C++ 实现 LeetCode Hot 100 题目 #### 计算二进制表示中前 N 数字的汉明重量 为了计算给定整数 `n` 的范围内所有数字的汉明重量（即二进制表示中的 '1' 的数量），可以利用位运算技巧来优化算法效率。当遇到偶数时，其汉明重量等于该数除以二后的汉明重量；奇数则在其前一个数的基础上加一。 ```cpp class Solution { public: vector<int> countBits(int n) { vector<int> ans(n + 1); ans[0] = 0; for (int i = 1; i < n + 1; ++i) { if (i % 2 == 0) { ans[i] = ans[i / 2]; } else { ans[i] = ans[i - 1] + 1; } } return ans; } }; ``` 此方法的时间复杂度为 O(N)，空间复杂度同样为 O(N)[^1]。 #### 查找数组中消失的数字 针对寻找 `[1, n]` 中缺失的正整数这一问题，可以通过原地标记的方法，在不额外占用大量内存的情况下完成任务。具体做法是对遍历过的索引位置做标记，最后未被访问的位置对应的索引即为所求解。 ```cpp class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { for (auto& num : nums) { int idx = abs(num) - 1; if (nums[idx] > 0) nums[idx] *= -1; } vector<int> res; for (size_t i = 0; i < nums.size(); ++i) { if (nums[i] > 0) res.push_back(i + 1); } return res; } }; ``` 这种方法巧妙地运用了输入数据本身的特性来进行操作，从而实现了线性的平均时间性能。 #### 寻找两数之和的目标组合 解决经典的 Two Sum 问题是通过哈希表加速查找过程的经典案例之一。借助于无序映射结构可以在一次扫描过程中同时记录已读取数值及其对应下标，并即时判断当前处理项是否存在匹配伙伴形成目标总和。 ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); ++i) { if (m.count(target - nums[i])) { return {i, m[target - nums[i]]}; } m[nums[i]] = i; } return {}; } }; ``` 上述代码片段展示了如何高效定位满足条件的一对元素，整体流程仅需单次遍历即可达成目的，显著提升了执行速度[^2]。 #### 处理链表相交节点检测 对于涉及链表的操作而言，双指针技术是一种非常有效的策略。特别是面对环形或交叉路径等问题场景时尤为适用。下面的例子说明了怎样确定两条可能相互连接的单向列表之间的交汇点： ```cpp ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { auto p1 = headA, p2 = headB; while(p1 != p2){ p1 = !p1 ? headB : p1->next; p2 = !p2 ? headA : p2->next; } return p1; } ``` 这段程序采用交替前进的方式让两个游走者最终同步到达相遇之处或是共同终点 null ，以此判定是否有公共部分存在[^3].