3

型の反転をカウントするアルゴリズムが必要です。a のインデックスが小さく、a > 2b の場合、a と b の間の反転が存在します。

O(n logn) でそれを行うアルゴリズムを考えられますか?

4

3 に答える 3

2

これは、マージソートアルゴリズムを少し調整することで実行できます。配列内の反転をカウントする

マージフェーズ中の通常の標準アルゴリズムでは、左半分と右半分の要素を比較し、左部分に残っている要素の数だけ反転を増やします。ここでは、左半分に残っている要素の数ではなく、2倍以上大きい左半分に残っている要素の数だけ増分します。

于 2012-10-02T03:08:22.613 に答える
0 
A[1..n]
B[1..n] = copy(A)
sort(B) //n*log(n)

for i = 1 to n-1
  //log(n)
  exists = specialBinarySearch(B, A[i], 1, n)

  //log(n)    
  setHighest(B, A[i], 1, n)
  if exists
    count++

specialBinarySearch(a, key, from, to)
  if from <= to
    mid = from + (to-from)/2

    if a[mid] < floor(key/2)
      return true
    else //must go to left of it to get even smaller value
      specialBinarySearch(a, key, from, mid-1)
  else
    return false

setHighest(a, key, from, to)
  if from <= to
    mid = from + (to-from)/2
    if a[mid] == key
      a[mid] = INT_MAX
    else if a[mid] < key
      setHighest(a, key, mid+1, to)
    else
      setHighest(a, key, from, mid-1)

わかった。というわけで、大まかな手順は以上です。

  1. 補助配列 B にコピーします。この O(n)
  2. 任意の n*log nアルゴリズムで並べ替え
  3. A の各要素に対してa、B で となる要素を求めて二分探索を実行しB[i]ますa > 2*B[i]。O(ログn )。(オーバーフローを避けるために私が書いたアルゴリズム)
  4. 考慮しなくてもよいのでB[i]、 を設定して比較対象外にしますB[i] = infinity。別の二分探索。O(ログn )
  5. 3と4を飽きるまで繰り返す。

だから、私たちが持っている計算しましょう

   O(n) + O(n*log(n)) + n*O(log(n))
=> O(n*log(n)) asymptotically
于 2012-10-02T04:00:21.570 に答える
0

これは、動的注文統計データ構造を使用して解決できます。このような構造の 2 つの選択肢を知っています。

  1. 注文統計ツリー
  2. インデックス可能なスキップリスト

配列 ( ) の各要素について、順序統計データ構造でb値のランクを見つけます。2b次にb、注文統計データ構造に挿入します。

値のランクは、より低いインデックスを持ち、より小さい2b要素の数を示します。これらの数の合計が「反転」の数になります。a2b

于 2012-10-02T09:16:42.700 に答える