高速配列の簡単な応用

問題の説明

配列が与えられたとき、k番目に小さい数を求めなさい。

アイデアの分析

高速ランキングのアイデアの助けを借りて、左側の分割後に右側以下でなければならないので、唯一のkを判断する必要があり、2つの部分の左と右の部分の大きさの分割を判断することができますどちらを探し続けるには、また、バイナリアルゴリズムに似ています。

核心

高速ランキングアルゴリズムのアイデアと組み合わせることで、問題を考慮して、配列を並べ替える必要はありません、ちょうどk番目の最小の数を見つける必要があることができますので、毎回分割することができ、左側と右側と比較して、どちらの側に結果を判断する、バイセクションアルゴリズムに似ています。判定は、kと比較の左側と右側の数に基づいており、kは右側の結果の数の左側の数よりも大きく、逆に、左側です。

時間の複雑さ

<=x,右边 >第1層はn（配列を分割し、左＝xとなる）、第2層はn÷2、第3層はn÷4、といった具合です。

n + n / 2 + n / 4 + ... = O(2n)

時間の複雑さはO(2n)

コーディング

#include <iostream>
using namespace std;
const int N = ;
int quick_sort(int q[], int l, int r, int k)
{
 if(l == r) return q[l];
 
 int i = l - 1, j = r + 1, x = q[l + r >> 1];
 while(i < j)
 {
 do i++; while(q[i] < x);
 do j--; while(q[j] > x);
 if(i < j) swap(q[i], q[j]);
 }
 //k番目に小さい数を求めればよいので、両辺をソートする必要はなく、左辺は右辺以下でなければならない。
 int sl = j - l + 1; 
 if(k <= sl) return quick_sort(q, l, j, k); //左側の数がk以上であれば、結果は左側になる。
 else return quick_sort(q, j + 1, r, k - sl);//左側がkより小さい数、右側がその結果である。
}
int main()
{
 int n, k;
 cin >> n >> k;
 
 int q[n];
 for(int i = 0; i < n; i++) cin >> q[i];
 
 cout << quick_sort(q, 0, n - 1, k) << endl;
 
 return 0;
}