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;
}
}
```