题解 | #两个升序数组的中位数#
两个升序数组的中位数
https://www.nowcoder.com/practice/b3b59248e61f499482eaba636305474b
#include <climits> #include <vector> class Solution { public: int getKElement(vector<int> nums1, vector<int> nums2, int k) { int i = 0, j = 0; int n = nums1.size(), m = nums2.size(); int res; while (i + j < k) { if (i < n && j < m) { if (nums1[i] < nums2[j]) { res = nums1[i++]; } else if (nums1[i] > nums2[j]) { res = nums2[j++]; } } else if (j < m) { res = nums2[j++]; } else { res = nums1[i++]; } } return res; } int getKthElement(vector<int> &nums1, int i, vector<int> nums2, int j, int k) { if (i >= nums1.size()) return nums2[j + k - 1]; if (j >= nums2.size()) return nums1[i + k - 1]; if (k == 1) return min(nums1[i], nums2[j]); int mid1 = i + k/2 - 1 < nums1.size() ? nums1[i + k/2 - 1] : INT_MAX; int mid2 = j + k/2 - 1 < nums2.size() ? nums2[j + k/2 - 1] : INT_MAX; if (mid1 < mid2) { return getKthElement(nums1, i + k/2, nums2, j, k-k/2); } else { return getKthElement(nums1, i, nums2, j + k/2, k-k/2); } } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums1 int整型vector * @param nums2 int整型vector * @return double浮点型 */ double Median(vector<int>& nums1, vector<int>& nums2) { // write code here int n = nums1.size(), m = nums2.size(); int mid; double res; if ((m + n) % 2 == 0) { mid = (m + n) / 2; res = (getKthElement(nums1, 0, nums2, 0, mid) + getKthElement(nums1, 0, nums2, 0, mid + 1)) / 2.0; } else { mid = (m + n) / 2 + 1; res = getKthElement(nums1, 0, nums2, 0, mid) / 1.0; } return res; } };