当前位置： 面试刷题>> 两个排序数组合的第k小元素 (经典算法题500道)
### 题目描述补充
题目：给定两个已排序的整数数组 `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 示例代码
```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 示例代码
```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 示例代码
```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
// 码小课网站中有更多相关内容分享给大家学习
```