编程面试题（数组反转）

Question

可能是重复问题：
计算数组中的逆序数

这是我几个月前参加开发者职位面试时遇到的一个编程问题。

给定一个由N个整数组成的数组A，数组的一个逆序对被定义为任意一对索引(a,b)，满足a<b且A[b]<A[a]。

编写一个函数：

int inversion_count(int A[], int n);

这个函数计算数组A中逆序对的数量，如果逆序对数量超过1,000,000,000，则返回-1。例如，在以下数组中：

A[0]=-1 A[1]=6 A[2]=3 A[3]=4 A[4]=7 A[5]=4

有四种反转：

(1,2)  (1,3)  (1,5)  (4,5)

所以函数应该返回4。 我用了一种很常见的方法来解决这个问题：使用双重循环。

int i, j;
long count;
for (i = 0; i < n; i++) {
   for (j = i+1; j < n; j++) {
      if (A[i] > A [j]) count++;
      if (count > 1000000000) break; // exit loop
   }
   if (count > 1000000000) break; // exit loop
}
if (count > 1000000000) return -1;
else return count;

所以它的运行时间是：O（n平方），我被告知这不够高效。我现在正在考虑用不同的方式解决这个问题，也许使用一个n log n算法，但我还没有想出来。有什么想法吗？

- all_by_grace

---

给定一个由N个整数组成的数组A，数组的逆序对是一对索引(a,b)，使得a ???。请问您能否填写“???”吗？看起来您遗漏了句子的结尾。 - David Hammen

你能完成这个语句的填写吗？“给定一个由N个整数组成的数组A，数组的反转是指一个索引对(a,b)，其中a”——什么是反转的定义？ - pstrjds

@Justin 感谢 Justin Ethier 编辑了这篇文章。我放了一个小于号，但忘记将其标记为代码格式，因此 HTML 编码器将其视为 HTML 标签。抱歉！ - all_by_grace

Answer 1

这个答案解释了一个O(n log n)的算法：计算数组中逆序对的个数。

其中的关键是先进行排序（O(n log n)），然后利用二分搜索来找到元素（同样是O(n log n)），从而得到O(n log n)的时间复杂度。

- orlp

---

请将以下有关编程的内容从英语翻译成中文。仅返回翻译后的文本：如果是重复内容，请投票关闭，不要复制粘贴答案。 - amit

我会两者兼顾，将我的答案删除并提供摘要。 - orlp

谢谢，我应该查一下的。为此道歉。 - all_by_grace