東北大学 工学研究科 電気・情報系 2016年8月実施 基礎科目 問題4 情報基礎2

标签：

• Tohoku-University
• Binary-Search
• Two-Pointers
• Hash-Table

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

日本語版

$m$ 個の互いに異なる整数 $A[0],A[1],\ldots,A[m-1]$ を要素とする配列 $A$ と，$n$ 個の互いに異なる整数 $B[0],B[1],\ldots,B[n-1]$ を要素とする配列 $B$ が与えられたとき，両方の配列に共通して存在する要素を全て出力する問題 $P$ を考える。次の問に答えよ。

(1) 問題 $P$ を $O(mn)$ 時間で解くアルゴリズムの概略を数行程度で記述せよ。

(2) 配列 $B$ の要素を整列させるとき，その時間計算量が $O(n\log n)$ となる整列アルゴリズムの名称を $1$ つ挙げよ。

(3) 配列 $B$ の要素があらかじめ昇順に整列されていると仮定する。この仮定を利用して，問題 $P$ を問 (1) のアルゴリズムよりも効率的に解くアルゴリズムの概略を数行程度で記述し，その時間計算量を与えよ。ただし，配列 $A$ の要素を並び替えてはいけない。

(4) 配列 $A$ と配列 $B$ の要素があらかじめ昇順に整列されていると仮定する。問題 $P$ を $O(m+n)$ 時間で解くアルゴリズムを $20$ 行以内の擬似コードとして記述せよ。

(5) 配列 $A$ と配列 $B$ の要素が整列されていない場合でも，あるデータ構造を用いることで，問題 $P$ を $O(m+n)$ 時間で解くアルゴリズムを設計できる。データ構造の名前を挙げたうえで，そのアルゴリズムの概略を数行程度で記述せよ。ただし，配列 $A$ と配列 $B$ の要素の最大値は $10(m+n)$ 以下であると仮定する。

题目描述

数组 $A[0],\ldots,A[m-1]$ 内有 $m$ 个互异整数，数组 $B[0],\ldots,B[n-1]$ 内有 $n$ 个互异整数。问题 $P$ 要求输出同时出现在两个数组中的全部元素。

1. 简述一个 $O(mn)$ 算法。
2. 给出一种能在 $O(n\log n)$ 时间内排序 $B$ 的算法名称。
3. 若 $B$ 已升序排列，且不能交换 $A$ 中的元素，给出较 (1) 高效的算法及复杂度。
4. 若 $A,B$ 均已升序排列，用不超过 $20$ 行伪代码给出 $O(m+n)$ 算法。
5. 即使两数组均未排序，也可利用数据结构求解。给出该数据结构和 $O(m+n)$ 算法。题面给定两数组元素的最大值不超过 $10(m+n)$。

Kai

(1)

对每个 $A[i]$ 遍历 $B$；若发现 $A[i]=B[j]$，输出 $A[i]$ 并结束该次内层遍历。比较次数至多 $mn$，故为 $O(mn)$。

(2)

归并排序（最坏时间 $O(n\log n)$）。

(3)

对每个 $A[i]$ 在 $B$ 中二分查找，命中则输出。无需改变 $A$，总时间为 $\boxed{O(m\log n)}$，额外空间 $O(1)$。

(4)

i = 0
j = 0
while i < m and j < n:
    if A[i] < B[j]:
        i = i + 1
    else if A[i] > B[j]:
        j = j + 1
    else:
        output(A[i])
        i = i + 1
        j = j + 1

每步至少前移一个指针，各指针最多前移一次整个数组，因此总时间 $O(m+n)$、额外空间 $O(1)$。

(5)

使用散列表：把 $B$ 中所有键插入集合 $H$，再遍历 $A$；若 $A[i]\in H$，则输出。保持散列表装载因子有界，在均匀散列假设下，单次插入与查询期望为 $O(1)$，因此

$$\boxed{\text{期望时间 }O(m+n),\qquad\text{空间 }O(n).}$$

此方案同样适用于负整数。

若键范围为 $0,\ldots,10(m+n)$，则可用布尔直接寻址表替代散列表：先全部置零，再标记 $B$ 中各值，最后扫描 $A$ 查表。此时最坏时间和空间均为 $O(m+n)$。