配列中でk番目に小さい要素を見つける,O(N)の関数
スポンサーリンク
珠玉のプログラミングの問題をやってます. コラム11の問題のなかで,「配列中でk番目に小さい要素を見つける関数で,O(N)のものを 作れ」というのがあったので解いてみました.
結構悩んだんですけど,要はクイックソートを片側のみ行うようにすれば解けます. 処理としては,とりあえずクイックソートを行って配列を分割.小さい方の部分配列の数が kより小さかったら,k番目に小さいものは大きいのほうの部分配列に在ります.逆に,小さい方の部分配列の数がkより大きかったら,k番目に小さいものはその配列中に在るはずです. よって,あとは目的の要素があると思われる部分配列だけまたクイックソートの分割をすればいい,ということになりますので,計算量はクイックソートよりずっと落ちます. どのぐらいになるかというと,最初がn個の分割,次が平均で1/2 * n個の部分配列の分割,その次が1/2 * 1/2 * nの部分配列の分割…とやっていくと,
n + 1/2 * n + 1/4 * n + ... < 2n
となるので,計算回数はO(n)で達成できます.しかし,最悪の場合はO(n2)かかりますね.
ソース
javascriptで書いてます.
/** * k番目に小さい数値を見つける * @param x 配列 * @param k 指定順位 */ function searchLankK(x, k) { /** * 片側のみのクイックソート * @param l ソート範囲の最小インデックス * @param u ソート範囲の最大インデックス * @param k 指定順位 */ function selectOne(l, u, k) { if (l >= u) return; var t = x[l], m = l; /* tはピボット,mは境界*/ /* ピボットを元に並べ替え */ for (var i = l + 1; i <= u; i++) { if (x[i] < t) { var temp = x[i]; /* swap */ x[i] = x[++m]; x[m] = temp; } } var temp = x[m]; /* swap */ x[m] = x[l]; x[l] = temp; /* ピボットより小さい要素がk個に収まるかを見る*/ if (m < k) { /* k番目はピボットより大きい範囲に在る */ selectOne(m + 1, u, k); } else if (m > k) { /* k番目はピボットより小さい範囲に在る */ selectOne(l, m, k); } /* m == kならなにもしない */ } k--; /* 配列は0から始めるので,kをそれに合わせる */ selectOne(0, x.length-1, k); /* 配列全体についてselectOne実行 */ return x[k]; /* k番目の値を返す */ }
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
- 作者: ジョンベントリー,Jon Bentley,小林健一郎
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/10
- メディア: 単行本
- 購入: 30人 クリック: 551回
- この商品を含むブログ (162件) を見る