给定两个长度为 n 和 m 的升序数组(后一个数一定大于等于前一个数),请你找到这两个数组中全部元素的中位数。
数据范围: ,数组中的元素满足
public double Median (ArrayList<Integer> nums1, ArrayList<Integer> nums2) { // write code here // write code here ArrayList<Integer> sumList = new ArrayList<>(nums1.size() + nums2.size()); int index1 = 0, index2 = 0; while (index1 < nums1.size() && index2 < nums2.size()) { Integer left = nums1.get(index1); Integer right = nums2.get(index2); if (left < right) { sumList.add(left); index1++; } else { sumList.add(right); index2++; } } // nums2 有剩余 if (index1 == nums1.size()) { for (int i = index2; i < nums2.size(); i++) sumList.add(nums2.get(i)); } else { // nums1 有剩余 for (int i = index1; i < nums1.size(); i++) sumList.add(nums1.get(i)); } int resLen = sumList.size(); // 返回奇偶下标 return (resLen & 1) == 1 ? sumList.get(resLen / 2) : (sumList.get(resLen / 2 - 1) + sumList.get(resLen / 2)) / 2.0; }
public double Median (ArrayList<Integer> nums1, ArrayList<Integer> nums2) { // write code here nums1.addAll(nums2); Collections.sort(nums1); int n=nums1.size(); double t=0; if(n%2 ==0) t=(double)(nums1.get(n/2 -1)+ nums1.get(n/2))/2; else t=nums1.get(n/2); return t; }
class Solution {
public:
int findKth(vector<int>::const_iterator A, int m, vector<int>::const_iterator B, int n, int k) { if (m > n) return findKth(B, n, A, m, k); if (m==0) return B[k-1]; if (k==1) return min(A[0], B[0]); int ia = min(m, k/2), ib = k - ia; if (A[ia-1] < B[ib-1]) { return findKth(A + ia, m - ia, B, n, k - ia); } else if (A[ia-1] > B[ib-1]) { return findKth(A, m, B + ib, n - ib, k - ib); } else { return A[ia-1]; } } double Median(vector<int>& nums1, vector<int>& nums2) { // write code here int m = nums1.size(); int n = nums2.size(); int total = m + n; if (total & 1) { return findKth(nums1.begin(), m, nums2.begin(), n, total/2+1); } else { return (findKth(nums1.begin(), m, nums2.begin(), n, total/2+1) + findKth(nums1.begin(), m, nums2.begin(), n, total/2)) * 0.5; } }
};