c - 编程面试题(数组倒置)-6ren

c - 编程面试题(数组倒置)

转载作者：行者123 更新时间：2023-12-02 04:07:43

Possible Duplicate:
Counting inversions in an array

这是我几个月前接受一家公司面试开发人员职位时遇到的编程问题。

给定一个由N个整数组成的数组A，该数组的求反定义为任意一对索引(a，b)，使得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(nsquare)，并被告知效率不高。我现在正在考虑解决该问题的另一种方法，也许使用 n log n 算法，但是我还没有弄清楚。有任何想法吗？