Untitled

mail@pastecode.io avatar
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;
    }
}