2

几天来，我一直在努力想出遵循下面伪代码的代码，以计算未排序的排列数列表的反转次数。我需要算法在 O(nlogn) 时间内运行，但我只能在 O(n^2logn) 时间内想到一个解决方案。

更具体地说，我想知道如何通过不使用嵌套的 for 循环来加快第二步。我知道还有其他有效的算法（即合并排序）可以工作，但我需要遵循伪代码的步骤。

Instance: An array A[1] . . . A[n], a permutation of n numbers 1, . . . , n
Question: Calculate vector B[j] = |{A[i] : j > i and A[i] > A[j]}| (the same as 
          B[j] = |{i : j > i and A[i] > A[j]}|) B[j] is the number of element 
          larger than A[j] to the left of A[j] in t the array A. In other words, 
          the sum of the elements in B is equal to the number of inversions in 
          the permutation A[1] . . . A[n].
(1) Initialize B[i] to 0.
(2) For each even A[j] find elements with indices smaller than j that are by one larger
than A[j]: increase B[j] by the number of such elements;
(3) Divide each A[i] by 2 (in the integer sense);
(4) Stop when all A[i] are 0.

以下是我到目前为止提出的代码：

long long numInversions = 0;     
// number of elements that are zero in the array
unsigned int zeros = 0;

do {

   // solution will need to replace this nested
   // for loop so it is O(n) not O(n^2)
   for (int i = 0; i < permNumber; i++){

           // checks if element is even
           if(array[i] % 2 == 0){
                  for (int j = i; j >= 0; j--){
                         if (array[j] == array[i] + 1){
                                numInversions++;
                         }
                 }
           }

      }

     // resets value of zeros for each pass
     zeros = 0;

     for (int k = 0; k < permNumber; k++){
             array[k] = array[k] / 2;
             if (array[k] == 0)
                  zeros++;


      }

} while(zeros != permNumber);

注意：该算法应返回列表中的反转数，一个标量。伪代码要求一个数组，但最后将数组的元素相加以计算反转计数。

Example: Consider a permutation (2, 3, 6, 1, 3, 5) with six inversions. The 
above algorithm works as follows:
2 4 6 1 3 5        (no pairs)                                  ÷2
1 2 3 0 1 2 1 =    0: one '1' to left, 2: one 3 to left        ÷2
0 1 1 0 0 1 1 =    0: two '1's to left, 0: two '1's to left    ÷2
0 0 0 0 0 0        total: 6 pairs
4

2 回答 2

2

这是一个非常聪明的算法——在每次迭代中，它计算将被除以 2 的反转数......虽然没有必要使用数组 for B，因为你所做的只是添加到元素然后求和他们起来。您可以只保留一个运行总和。

无论如何...为了加快步骤 (2)，您可以使用另一个数组C[v]来记住 中所有奇数值的计数A，如下所示：

Step 2:
   Initialize all C[v] to 0
   For i = 1 to n:  //0 to n-1 if you're using 0-based arrays
       if A[i] is even then:
           B[i] += C[A[i]+1]
       else:
           C[A[i]] += 1
于 2018-02-25T21:25:36.507 回答
0

在不使用归并排序的情况下，在 Java 中：

public int binarySearch(ArrayList<Integer> A, int s, int e, int elem){
        // finds the position at which elem can be inserted to maintain the sorted order in A
        if (s >= e){
            return elem >= A.get(s) ? s+1 : s;
        }
        int mid = (s+e)/2;
        if (elem == A.get(mid)) return mid+1;

        if (elem < A.get(mid)) return binarySearch(A, s, mid-1, elem); 
        return binarySearch(A, mid+1, e, elem);
    }
    public int binarySearchLast(ArrayList<Integer> A, int s, int e, int elem){
        // finds the index of first element greater than "elem" in list A
        if (s >= e) return elem < A.get(s) ? s : s+1;
        int mid = (s+e)/2;

        if (elem < A.get(mid)) return binarySearchLast(A, s, mid, elem); 
        return binarySearchLast(A, mid+1, e, elem);
    }
    public int countInversions(ArrayList<Integer> A) {
        int cnt = 0;
        ArrayList<Integer> B = new ArrayList<>();
        B.add(A.get(0));
        for (int i = 1; i < A.size(); i++){
            int idx = binarySearch(B, 0, B.size()-1, A.get(i));
            B.add(idx, A.get(i));
            idx = binarySearchLast(B, 0, B.size()-1, A.get(i));
            cnt = cnt + B.size() - idx;
        }
        return cnt;
    }
于 2019-06-24T14:57:24.810 回答