algorithm - 用于计算数组中特定类型的反转的算法

Question

我需要一种计算类型反转的算法：如果 a 具有较低的索引且 a > 2b，则存在 a 和 b 之间的反转。

你能想到一个算法可以在 O(n logn) 中完成吗？

Answer 1

它可以通过合并排序算法中的一个小调整来完成。计算数组中的反转

在合并阶段的正常标准算法中，您比较左半部分和右半部分的元素，并通过左部分中剩余的元素数量增加反转。在这里，我们增加的不是左半部分剩余的元素数量，而是左半部分剩余元素的数量增加两倍以上。

Answer 2

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 ⁿ算法进行排序
3. 对于 A 中的每个元素a，在 B 中执行对任何元素的二分搜索，B[i]使得a > 2*B[i]. O(log ⁿ )。（我为避免溢出而编写的算法）
4. 由于我们不必B[i]考虑，通过设置使其不符合比较条件B[i] = infinity。另一个二分搜索。O(log ⁿ )
5. 重复 3 和 4 直到耗尽。

所以，让我们计算一下我们有

   O(n) + O(n*log(n)) + n*O(log(n))
=> O(n*log(n)) asymptotically

Answer 3

这可以使用动态订单统计数据结构来解决。我知道这种结构的两种选择：

1. 订单统计树
2. 可索引的跳过列表

对于按顺序排列的数组 ( ) 的每个元素，在顺序统计数据结构中b查找值的排名。2b然后插入b到订单统计数据结构中。

该值的等级给出了具有较低索引且小于2b的元素的数量。这些数字的总和给出了“反转”的数量。a2b