私はこの質問があります：
サイズnの2つのソートされたリスト（配列に格納されている）が与えられた場合、2つのリストの和集合でn番目に大きい要素を計算するO（log n）アルゴリズムを見つけます。
n番目に大きい要素が必要で、配列のサイズもnであるため、おそらくここにトリックがあることがわかりますが、それが何であるかはわかりません。カウントソートを適応できると思っていたのですが、うまくいくでしょうか？
質問する
4656 次
3 に答える
8
A [n/2]とB[n/2]を比較します。等しい場合、それらのいずれかが私たちの結果です。このアルゴリズムの他の停止条件は、両方の配列のサイズが1の場合です（最初またはいくつかの再帰ステップの後）。この場合、A [n/2]とB[n/2]の最大のものを選択します。
A [n / 2] <B [n / 2]の場合、A[]の後半とB[]の前半に対して、この手順を再帰的に繰り返します。
A [n / 2]> B [n / 2]の場合、B[]の後半とA[]の前半に対して、この手順を再帰的に繰り返します。
各ステップで問題のサイズが（最悪の場合）半分になるため、O（log n）アルゴリズムを取得します。
nインデックスを取得するために常に配列サイズを2で割ると、が2の累乗である場合にのみ正しく機能します。（任意の）インデックスを選択するより正しい方法はn、1つの配列に対して同じ戦略を使用しますが、他の配列に対しては補完的なインデックスを選択することj=n-iです。
于 2013-01-26T10:33:17.157 に答える
2
Evgeny Kluevは、より良い答えを示しています-私はそれらがソートされているとは考えていなかったので、私のものはO（n log n）でした。
私が追加できるのは、MITの厚意により、バイナリ検索を説明する非常に優れたビデオへのリンクを提供することです。
于 2013-01-26T10:33:40.067 に答える
1
public static void main(String[] args) {
int[] fred = { 60, 5, 7, 3, 20, 3, 44 };
int[] tmp = new int[fred.length];
go(fred, 1, tmp, 3);
}
public static void go(int[] fred, int cnt, int[] tmp, int whatPosition) {
int max = 0;
int currentPosition = 0;
for (int i = 0; i < fred.length; i++) {
if (i == 0)
max = fred[i];
else {
if (fred[i] > max) {
max = fred[i];
currentPosition = i;
}
}
}
System.arraycopy(fred, 0, tmp, 0, fred.length);
tmp[currentPosition] = 0;
cnt++;
if(cnt != whatPosition)
go(tmp, cnt, tmp, whatPosition);
else{
for (int i = 0; i < tmp.length; i++) {
if (i == 0)
max = tmp[i];
else {
if (tmp[i] > max) {
max = tmp[i];
}
}
}
System.out.println(max);
}
}
于 2013-03-21T07:48:07.040 に答える