配列の中で2番めに大きい要素

最近ブログを書いてないって言われたので,何かを書こうとおもったけれど,何を書くのが全く思いつかないので,今日,聞かれた質問について書こうと思う.

聞かれたのは,与えられた配列の中から2番めに大きい要素を知る方法である.1番大きい要素の取得の仕方はよくある話だが2番めはあまり聞いたことがない気がする.どうやって解くのが最も効率が良いだろうか.ちなみにプログラム演習の課題のようなので,あまり高度なライブラリを使用するのは避けなければいけないという制約がついている.

最も簡単な解法は,一番最大の要素をまず見つけ出し,次にその要素を取り除いた配列から最大の要素を取り出す方法だ.これは愚直だがわかりやすく書きやすい.ただし,最大値を求めるループを2回使う必要があり,いくらか冗長な気がする.次に,思いつくのはソートして2番めの要素を取り出す方法である.スクリプト言語を使っているのであればこれが一番ありがちなのではないだろうか.ただし,一から全て実装する場合は,これは少し面倒だ(ライブラリがまったくないそんな状態は普通ないのだが).

さてここではよりフォーマルな形で定式化することで,この問題を効率よく解く方法を考えたい.まず与えられた配列を\(a_n, \dots, a_1\)という数列であるとしよう.\(a_k, \dots, a_1\)の中で一番大きい要素を返す関数を\(f(k)\)とする.このとき明らかに
$$f(k) = \begin{cases}
-\infty & (k=0) \\
f(k-1) & (f(k-1) \geq a_{k}) \\
a_{k} & (otherwise)
\end{cases}$$
が成り立つ.次に,\(a_k, \dots, a_1\)の中で2番めに大きい要素を返す関数を\(g(k)\)としよう.定義から明らかに\(g(k) \leq f(k)\)である.\(g(k)\)の計算は\(f(k)\)と非常に近いはずである.しかし,2番めであるという制約が,問題を難しくしている.まず,\(g(k)\)と\(g(k-1)\),そして\(a_k\)の関係を考えよう.まず,\(a_k\leq g(k-1)\)のときは明らかに\(g(k)=g(k-1)\)である.次に,\(a_k> g(k-1)\)の場合は,\(g(k)=a_k\)としたいところだが,\(f(k)\)との兼ね合いがあるため,それだけでは条件として不十分だ.実際には,\(f(k-1) < a_k\)のときは,\(g(k)\ne a_k\)としなければ,2番めに大きいという条件を満たせない.逆に言えば,これだけで必要条件を満たすことができる.したがって,まとめれば
$$g(k) = \begin{cases}
-\infty & (k=0) \\
g(k-1) & (g(k-1) \geq a_{k}) \\
a_{k} & (f(k-1) \geq a_{k}) \\
g(k-1) & (otherwise)
\end{cases}$$
である.思ったより簡単だった.

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA