(归并第 k小)已知两个长度均为 n的有序数组 a1和 a2(均为递增序,但不保证严格单调递增),并且给定正整数 k (1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里第 k小的数值。 试补全程序。 #include <bits/stdc++.h> using namespace std; int solve(int *a1, int *a2, int n, int k) { int left1 = 0, right1 = n - 1; int left2 = 0, right2 = n - 1; while (left1 <= right1 && left2 <= right2) { int m1 = (left1 + right1) >> 1; int m2 = (left2 + right2) >> 1; int cnt = ①; if (②) { if (cnt < k) left1 = m1 + 1; else right2 = m2 - 1; } else { if (cnt < k) left2 = m2 + 1; else right1 = m1 - 1; } } if (③) { if (left1 == 0) { return a2[k - 1]; } else { int x = a1[left1 - 1], ④; return std::max(x, y); } } else { if (left2 == 0) { return a1[k - 1]; } else { int x = a2[left2 - 1], ⑤; return std::max(x, y); } }}
①处应填( )
(m1 + m2) * 2
(m1 - 1) + (m2 - 1)
m1 + m2
(m1 + 1) + (m2 + 1)
②处应填( )
a1[m1] == a2[m2]
a1[m1] <= a2[m2]
a1[m1] >= a2[m2]
a1[m1] != a2[m2]
.③处应填( )
left1 == right1
left1 < right1
left1 > right1
left1 != right1
④处应填( )
y = a1[k - left2 - 1]
y = a1[k - left2]
y = a2[k - left1 - 1]
y = a2[k - left1]
⑤处应填( )
y = a1[k - left2 - 1]
y = a1[k - left2]
y = a2[k - left1 - 1]
y = a2[k - left1]
发表评论