多题目


(归并第 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);
		}
	}}


第1题 单选

①处应填( )

A.

(m1 + m2) * 2

B.

(m1 - 1) + (m2 - 1)

C.

m1 + m2

D.

(m1 + 1) + (m2 + 1)

第2题 单选

②处应填( )

A.

a1[m1] == a2[m2]

B.

a1[m1] <= a2[m2]

C.

a1[m1] >= a2[m2]

D.

a1[m1] != a2[m2]

第3题 单选

.③处应填( )

A.

left1 == right1

B.

left1 < right1

C.

left1 > right1

D.

left1 != right1

第4题 单选

④处应填( )

A.

y = a1[k - left2 - 1]

B.

y = a1[k - left2]

C.

y = a2[k - left1 - 1]

D.

y = a2[k - left1]

第5题 单选

⑤处应填( )

A.

y = a1[k - left2 - 1]

B.

y = a1[k - left2]

C.

y = a2[k - left1 - 1]

D.

y = a2[k - left1]

发表评论

登录 后再回复