mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-03 14:15:40 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
87 lines
4.9 KiB
Markdown
87 lines
4.9 KiB
Markdown
# 練習問題
|
|
|
|
## 知識の確認
|
|
|
|
### 10 をヒープに挿入した後の調整
|
|
|
|
配列 `[9, 7, 8, 3, 5]` は最大ヒープを表します。このヒープに 10 を挿入します。
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. まず 10 を配列の末尾に追加すると、その親ノードの値はいくつですか。
|
|
2. 新しいノードから上方向にヒープ化します。各交換後の配列を書いてください。
|
|
3. 最終的なヒープの先頭要素はいくつですか。交換は全部で何回行いましたか。
|
|
|
|
??? success "解答例"
|
|
|
|
1. 追加した 10 のインデックスは 5、その親のインデックスは
|
|
$\lfloor(5-1)/2\rfloor=2$ なので、親の値は 8 です。
|
|
|
|
2. 10 は 8 より大きいため、一回目の交換後は `[9, 7, 10, 3, 5, 8]` となります。
|
|
10 は親の 9 よりも大きいため、二回目の交換後は `[10, 7, 9, 3, 5, 8]` となります。
|
|
ここで 10 が根に達したので、ヒープ化を終えます。
|
|
|
|
3. 最終的なヒープの先頭は 10 で、交換回数は 2 回です。
|
|
|
|
### 最小ヒープの親子関係を確認する
|
|
|
|
配列 `[1, 4, 3, 7, 6, 2]` は完全二分木を表します。最小ヒープでは、各親ノードの値がその子以下である必要があります。
|
|
インデックス $i$ に対し、左右の子のインデックスはそれぞれ $2i+1$ と $2i+2$ です。
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. インデックス 2 の子のインデックスと値を、それぞれ答えてください。
|
|
2. インデックス 2 のノードの値は 3 です。子との関係は最小ヒープの規則に違反していますか。違反していれば、どの二つの要素を交換しますか。
|
|
3. 問い 2 で違反すると判断した場合は交換後の配列を書き、違反しない場合は交換が不要だと説明してください。最後に、残りの親子関係を確認してください。
|
|
|
|
??? success "解答例"
|
|
|
|
1. インデックス 2 の左の子はインデックス 5 で、値は 2 です。右の子のインデックスは 6 ですが、配列の長さが 6 なので、右の子はありません。
|
|
|
|
2. 親の値 3 が子の値 2 より大きく、最小ヒープの規則に違反するため、インデックス 2 と 5 の要素を交換します。
|
|
|
|
3. 交換後は `[1, 4, 2, 7, 6, 3]` です。一つずつ確認すると、
|
|
`1 ≤ 4`、`1 ≤ 2`、`4 ≤ 7`、`4 ≤ 6`、`2 ≤ 3` が成り立ちます。
|
|
すべての親が自分の子以下なので、最小ヒープの規則を満たしています。
|
|
|
|
### 最小ヒープで大きいほうから三つの数を保持する
|
|
|
|
データストリーム `[4, 1, 7, 3, 8]` から大きいほうから 3 個の数を保持するには、要素数が 3 以下の最小ヒープを使えます。
|
|
|
|
まず最初の 3 個を順に最小ヒープへ入れます。ヒープがいっぱいになったら、新しい数を読み込むたびに、
|
|
先頭より大きければ先頭を削除して新しい数を入れ、そうでなければ変更しません。
|
|
|
|
各数を読み込んだ後に、ヒープが保持する数と先頭の値を書いてください。
|
|
保持する数は集合で示せばよく、ヒープ配列内の並びを書く必要はありません。
|
|
|
|
??? success "解答例"
|
|
|
|
各数を読み込んだ後の結果は、次のとおりです。
|
|
|
|
| 読み込んだ数 | 保持する数 | ヒープの先頭 |
|
|
| --- | --- | --- |
|
|
| 4 | `{4}` | 4 |
|
|
| 1 | `{1, 4}` | 1 |
|
|
| 7 | `{1, 4, 7}` | 1 |
|
|
| 3 | `{3, 4, 7}` | 3 |
|
|
| 8 | `{4, 7, 8}` | 4 |
|
|
|
|
ヒープがいっぱいになると、先頭は現在保持している数の最小値です。新しい数が先頭より大きい場合にだけ、
|
|
先頭を新しい数で置き換えます。最後に残る `{4, 7, 8}` が、大きいほうから 3 個の数です。
|
|
|
|
## プログラミング演習
|
|
|
|
### 配列の k 番目に大きい要素を探す
|
|
|
|
整数配列 `nums` と整数 $k$ が与えられます。$1 \le k \le n$ を満たし、$n$ は配列の長さです。配列を降順に並べたとき、$k$ 番目の要素を返してください。
|
|
|
|
重複する要素も別々に数えます。例えば、`[5, 5, 2]` の 2 番目に大きい要素も 5 です。要素数が $k$ 以下の最小ヒープを使って解いてください。
|
|
|
|
??? tip "解くためのヒント"
|
|
|
|
1. k 番目に大きい要素は、大きいほうから k 個の数の中で最小のものです
|
|
2. 各数をまず最小ヒープに挿入し、要素数が k を超えたら最小値を取り出します
|
|
3. 走査が終わると、ヒープには大きいほうから k 個の数が残り、先頭が答えになります
|
|
|
|
[LeetCode](https://leetcode.com/problems/kth-largest-element-in-an-array/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|