4

配列の各要素のランクを、同点の場合は平均して効率的に見つけるにはどうすればよいでしょうか? 例えば：

float[] rank(T)(T[] input) {
    // Implementation
}

auto foo = rank([3,6,4,2,2]);  // foo == [3, 5, 4, 1.5, 1.5]

私が考えることができる唯一の方法は、3 つの配列を割り当てる必要があります。

  1. ソートする必要があり、所有していないため、入力配列の複製。
  2. 入力配列がソートされた順序を追跡するための配列。
  3. 返すランクの配列。

O(N log N) の時間と O(1) の補助空間 (つまり、割り当てなければならない唯一の配列は、返される配列だけです) でこれを行う方法を知っている人はいますか?上記の3つの配列？

4

7 に答える 7

5

返す配列を割り当て (R と呼びましょう)、0..n-1 に初期化してから、着信配列 (I と呼びます) を「並べ替える」ことができますが、比較 I[R[k]] vs . I[R[j]] 通常の R[k] 対 R[j] の代わりに、必要に応じて R 配列の値を交換します (通常の I 配列の値の代わりに)。

クイックソートまたはヒープソート（またはバブルソートですが、複雑さが台無しになります）を使用して、この間接ソートを実装できます。

1 つの配列と、インデックス用のスタック スペースを割り当てるだけで済みます。

于 2009-11-04T15:37:28.143 に答える
2

わかりましたので、入力配列を に複製しますfoo。heapsortfooを使用して O(n log n) 時間でその場でソートします。次に、入力配列の最初の要素を取得し、バイナリ検索を使用して O(log n) 時間でそのランクを見つけ、ランクを配列に挿入して返します。fooranks

3 つではなく 2 つの配列を使用するようになりました。

于 2009-11-04T15:36:29.160 に答える
0

私はPythonで素早く汚いことをするためにこれを使用しました:

def rank(X):
    B = X[:]
    B.sort()
    return [ float(B.index(x)+1) for x in X]

def rank(X):
    B = X[:]
    B = list(set(B))
    B.sort()
    return [ float(B.index(x)+1) for x in X]

最初の例は、元のリストに重複がない場合に機能します。もっとうまくやることができますが、私はいくつかのハックで遊んでいて、これを思いつきました。重複がある場合、2番目のものは機能します。

于 2016-12-27T19:27:11.150 に答える
0

おそらく、フローリンの回答(および関連するコメント) を簡単なコードで 要約すると便利でしょう。

Rubyでそれを行う方法は次のとおりです。

arr = [5,1,0,3,2,4]
ranks = (0..arr.length-1).to_a.sort_by{ |x| arr[x] }
# ranks => [2, 1, 4, 3, 5, 0]

そしてPythonで：

arr = [5,1,0,3,2,4]
ranks = range(len(arr))
ranks.sort(key=lambda x:arr[x])
# ranks => [2, 1, 4, 3, 5, 0]

ranks 配列は、0 はランク 2、1 はランク 1、2 はランク 4 などを示します (もちろん、これらのランクは 1 ではなく 0 から始まります)。

于 2009-11-05T13:55:58.857 に答える
0

配列を所有していない場合、O(N log N) と空間 O(1) でそれを行うことはできないと思います。

要素の範囲 (要素の大きさ) が小さい場合は、カウントを使用します。各要素がいくつあるかをカウントし、カウント配列を使用して入力配列に基づいて結果配列を計算します。

c - is counting result,
C - is cumulative counting
C[i] = c[i] + c[i-1] + c[i-2] + ... + c[0]
result[i] = 1 / c[in[i]] + C[in[i]-1]
于 2009-11-04T15:14:24.400 に答える
0

配列をコピーしてソートし、そこから移動してみませんか? ヒープソートなど、利用可能なインプレースソートアルゴリズムがたくさんあります。

于 2009-11-04T15:36:00.747 に答える