int 数组的最佳反转计数

发布于 2024-11-07 19:20:37 字数 483 浏览 0 评论 0原文

今天我在看当地信息学奥林匹克竞赛的最新考试，我发现了一个有趣的问题。简而言之，它要求给定一个整数数组，计算它有多少个反转，其中反转是一对索引 i, j 使得 i > ; j 和 A[i] A[j]。非正式地，反转的数量是无序对的数量。最初我做了一个 O(n²) 解决方案（是的，这是一个天真的解决方案），但是看到它与输入的大小不太适合，我对这个问题进行了更多的思考，然后我意识到可以通过合并排序的变体在 O(n log n) 时间内完成此操作，该变体可以很好地处理输入的大小。

但是看到输入约束（1 和 M 之间的 n 个整数，并且没有重复项），我想知道我的解决方案是否是最佳的，或者您知道是否还有其他解决方案解决这个问题的方法是击败 O(n log n) 运行时间？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

坏尐絯℡ 2024-11-14 19:20:38

文献中最好的结果是 O(n √(log n)) 算法，因为陈和帕特拉斯库。不知道常数。

回复收藏 0 原文

野却迷人 2024-11-14 19:20:38

据我所知，O(n log n) 是最好的。

这里给出了详细的解释：

http://www.geeksforgeeks.org/counting-inversions/

回复收藏 0 原文

怪我太投入 2024-11-14 19:20:38

如果我们假设用于表示整数的位数是恒定的（例如 32 或 64 位），则可以在 O(N) 时间内解决这个问题。

这是一个 python 实现示例。

http://ideone.com/g57O87


def inv_count(a, m=(1<<32)):
  if not m or not a:
      return 0
  count = 0
  ones = []
  zeros = []
  for n in a:
    if n & m:
      ones.append(n & ~m)
    else:
      count += len(ones)
      zeros.append(n & ~m)
  m /= 2
  return count + inv_count(ones, m) + inv_count(zeros, m)

打印 inv_count([1, 2, 3, 4, 5])
打印 inv_count([5, 4, 3, 2, 1])

我们能够实现小于 O(N x Log(N)) 的时间复杂度，因为我们使用非比较排序算法（基数排序）背后的思想来获取计数。

If we assume the number of bits used to represent the integer is constant (say 32 or 64 bits), this can be solved in O(N) time.

Here is an example python implementation.

http://ideone.com/g57O87


def inv_count(a, m=(1<<32)):
  if not m or not a:
      return 0
  count = 0
  ones = []
  zeros = []
  for n in a:
    if n & m:
      ones.append(n & ~m)
    else:
      count += len(ones)
      zeros.append(n & ~m)
  m /= 2
  return count + inv_count(ones, m) + inv_count(zeros, m)

print inv_count([1, 2, 3, 4, 5])
print inv_count([5, 4, 3, 2, 1])

We are able to achieve less than O(N x Log(N)) time complexity, as we are using idea behind a non-comparative sorting algorithm, radix sort, to get the count.

回复收藏 0 原文

~没有更多了~