题目描述补充

题目：给定两个已排序的整数数组 nums1 和 nums2，以及一个整数 k，请编写一个函数来找出并返回这两个数组中的第 k 小元素。元素的索引从 1 开始计数。

注意：

• 你可以假设 k 总是有效的，即 1 ≤ k ≤ 数组元素总和。
• 两个数组均为升序排列。

示例

假设 nums1 = [1, 3, 5, 7]，nums2 = [2, 4, 6, 8]，k = 3。

那么，两个数组合并后的排序为 [1, 2, 3, 4, 5, 6, 7, 8]，第 3 小的元素是 3。

PHP 示例代码

function findKthElement($nums1, $nums2, $k) {
    $m = count($nums1);
    $n = count($nums2);
    $index1 = 0;
    $index2 = 0;

    while (true) {
        // 防止数组越界
        if ($index1 == $m) return $nums2[$index2 + $k - 1];
        if ($index2 == $n) return $nums1[$index1 + $k - 1];
        if ($k == 1) return min($nums1[$index1], $nums2[$index2]);

        // 确定下一步的搜索区间
        $newIndex1 = min($index1 + floor($k / 2) - 1, $m - 1);
        $newIndex2 = min($index2 + floor($k / 2) - 1, $n - 1);
        if ($nums1[$newIndex1] <= $nums2[$newIndex2]) {
            $k -= ($newIndex1 - $index1 + 1);
            $index1 = $newIndex1 + 1;
        } else {
            $k -= ($newIndex2 - $index2 + 1);
            $index2 = $newIndex2 + 1;
        }
    }
}

// 示例调用
$nums1 = [1, 3, 5, 7];
$nums2 = [2, 4, 6, 8];
$k = 3;
echo findKthElement($nums1, $nums2, $k);  // 输出: 3

Python 示例代码

def findKth(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    index1, index2 = 0, 0

    while True:
        # 边界情况
        if index1 == m:
            return nums2[index2 + k - 1]
        if index2 == n:
            return nums1[index1 + k - 1]
        if k == 1:
            return min(nums1[index1], nums2[index2])

        # 确定下一步的搜索区间
        newIndex1 = min(index1 + k // 2 - 1, m - 1)
        newIndex2 = min(index2 + k // 2 - 1, n - 1)
        if nums1[newIndex1] <= nums2[newIndex2]:
            k -= (newIndex1 - index1 + 1)
            index1 = newIndex1 + 1
        else:
            k -= (newIndex2 - index2 + 1)
            index2 = newIndex2 + 1

# 示例调用
nums1 = [1, 3, 5, 7]
nums2 = [2, 4, 6, 8]
k = 3
print(findKth(nums1, nums2, k))  # 输出: 3

JavaScript 示例代码

function findKth(nums1, nums2, k) {
    let m = nums1.length;
    let n = nums2.length;
    let index1 = 0, index2 = 0;

    while (true) {
        // 边界情况
        if (index1 === m) return nums2[index2 + k - 1];
        if (index2 === n) return nums1[index1 + k - 1];
        if (k === 1) return Math.min(nums1[index1], nums2[index2]);

        // 确定下一步的搜索区间
        const newIndex1 = Math.min(index1 + Math.floor((k - 1) / 2), m - 1);
        const newIndex2 = Math.min(index2 + Math.floor((k - 1) / 2), n - 1);
        if (nums1[newIndex1] <= nums2[newIndex2]) {
            k -= (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1;
        } else {
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 1;
        }
    }
}

// 示例调用
const nums1 = [1, 3, 5, 7];
const nums2 = [2, 4, 6, 8];
const k = 3;
console.log(findKth(nums1, nums2, k));  // 输出: 3

// 码小课网站中有更多相关内容分享给大家学习