Untitled
unknown
c_cpp
2 years ago
1.6 kB
2
Indexable
Never
/* 请在这里填写答案 */ int getKthElement(int *nums1, int *nums2, int n1, int n2, int k) { int index1 = 0, index2 = 0; int kthElement = 0; while (true) { // 边界情况 if (index1 == n1) { return nums2[index2 + k - 1]; } if (index2 == n2) { return nums1[index1 + k - 1]; } if (k == 1) { return nums1[index1] < nums2[index2] ? nums1[index1] : nums2[index2]; } // 正常情况 int half = k / 2; int newIndex1 = (index1 + half < n1 ? index1 + half : n1) - 1; int newIndex2 = (index2 + half < n2 ? index2 + half : n2) - 1; int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= (newIndex1 - index1 + 1); index1 = newIndex1 + 1; } else { k -= (newIndex2 - index2 + 1); index2 = newIndex2 + 1; } } } int median(int *a, int *b, int n1, int n2, int lowa, int lowb) { int totalLength = n1 + n2; if (totalLength % 2 == 1) { int midIndex = totalLength / 2; double median = getKthElement(a, b, n1,n2,midIndex + 1); return median; } else { int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2; double median = (getKthElement(a, b,n1,n2,midIndex1 + 1) + getKthElement(a, b,n1,n2, midIndex2 + 1)) / 2.0; return median; } }