计算数组中的逆序对 | Baeldung中文网

1. Overview

In this tutorial, we’ll discuss the problem of counting inversions in an array. Firstly, we’ll define the problem and provide an example that explains the meaning of an inversion.

Secondly, we’ll discuss two approaches to solving the problem and talk about the good usage of the problem.

2. Defining the Problem

Suppose we have an array of integers, which are enumerated from to n - 1 . The value of the $i^{th}$ element is equal to A_i .

An inversion is a pair of indices (i, j) that satisfies the following:

$[\boldsymbol{A_i > A_j ; 0 \leq i < j \leq n - 1}]$

In other words, an inversion is a pair of two distinct indices such that the order of these two indices is the reverse order of their values.

The problem gives us an array and asks to compute the number of inversions in this array.

Let’s check the example for better understanding:

Suppose we have an array A = [1, 2, 3, 1, 2] . The answer in this case is because we have (1, 3) , (2, 3) and (2, 4) as inversions.

Note that when the array is sorted increasingly, the number of inversions is equal to . On the other hand, when the array is sorted decreasingly, the number of inversions is the maximum possible over all the permutations of the array (it will be equal to $(n \times (n - 1)) / 2$ when elements are pairwise distinct).

In other words, the number of inversions refers to how far the array is from being sorted.

3. Naive Approach

3.1. Main Idea

The idea is straightforward. We p****erform a brute force by iterating over all pairs of indices and check whether this pair satisfies the condition mentioned in section 2.

3.2. Implementation

Let’s take a look at the implementation:

algorithm NaiveCountInversions(A, n):
    // INPUT
    //   A = The array to process
    //   n = The size of array A
    // OUTPUT
    //   Returns the number of inversions in the array A

    answer <- 0
    for i <- 0 to n - 2:
        for j <- i + 1 to n - 1:
            if A[i] > A[j]:
                answer <- answer + 1
    return answer

Firstly, we initialize answer with zero, which will hold the resulting answer. Then, we start by iterating over the first element of the pair. Then, we iterate over the second element . Note that since we start from i + 1 , we guarantee that j > i .

Next, we check the pair (i, j) to see whether it satisfies the inversions condition or not. If yes then we have a new inversion, and we increase the total number of inversions by one.

Finally, we return the resulting answer .

The complexity of the naive approach is $\boldsymbol{O(n^{2})}$ , where is the length of .

4. Divide-And-Conquer Approach

4.1. Theoretical Idea

Suppose we want to count the number of inversions inside the array . Let’s divide it into two equal Arrays and call the first one and the second one . Now an inversion $\boldsymbol{(i, j)}$ can have one of the following types:

$\boldsymbol{i \in L}$ and $\boldsymbol{j \in R}$ .
$\boldsymbol{i \in L}$ and $\boldsymbol{j \in L}$ .
$\boldsymbol{i \in R}$ and $\boldsymbol{j \in R}$ .

Consider the first type. The problem turns out to computing for each index $i \in L$ , the number of indices $j \in R$ such that L_i > R_j .

Now suppose that both arrays $\boldsymbol{L}$ and $\boldsymbol{R}$ are sorted increasingly, then we can use the two-pointers technique to solve it. That’s because indices that satisfy the condition for an index always form a prefix from the array , when gets bigger, the length of the prefix increases.

But, what about the second and third types? The answer is simple: just perform the same algorithm recursively for both and independently.

Back to the first type, we supposed that both and are sorted increasingly. To achieve that, the algorithm must sort them. In other words, after applying the algorithm to both and , they become sorted. To sort $\boldsymbol{A}$ we just merge the two sorted arrays $\boldsymbol{L}$ and $\boldsymbol{R}$ into $\boldsymbol{A}$ .

4.2. Implementation

Let’s start by implementing a function that counts the number of inversions of the first type:

algorithm CountInvOfFirstType(L, R, lenL, lenR):
    // INPUT
    //   L = The left subarray
    //   R = The right subarray
    //   lenL = The length of the first subarray L
    //   lenR = The length of the second subarray R
    // OUTPUT
    //   Returns the number of inversions where the first element is in L and the second in R

    answer <- 0
    j <- 0
    for i <- 0 to lenL - 1:
        while j < lenR and R[j] < L[i]:
            j <- j + 1
        answer <- answer + j
    return answer

Firstly, we initialize answer with zero, which will hold the resulting answer. Then, we initialize with zero, which is the first index in the that breaks the condition for the current . More formally, it’s the first index such that $\boldsymbol{L_i \leq R_j}$ . Since we’re using zero-indexed arrays, $\boldsymbol{j}$ represents the length of the prefix from $\boldsymbol{R}$ that satisfies the condition.

While we increase , we must increase as well. This continues until it breaks the condition again.

After computing the correct , we add it to the answer as the number of elements in less than L_i .

Finally, we return the resulting answer .

Now, let’s take a look at the implementation of the complete algorithm:

algorithm DivideAndConquerCountInversions(A, n):
    // INPUT
    //   A = The array to process
    //   n = The size of array A
    // OUTPUT
    //   Returns the total number of inversions in the array A

    if n <= 1:
        return 0

    // Divide the array into two halves
    lenL <- n / 2
    lenR <- n - lenL
    L <- A[0: lenL-1]
    R <- A[lenL: n]

    // Recursively count inversions in each half
    answer <- countInv(L, lenL) + DivideAndConquerCountInversions(R, lenR)

    // Count inversions of the first type and merge both halves
    answer <- answer + CountInvOfFirstType(L, R, lenL, lenR)
    merge(A, L, R, lenL, lenR)

    return answer

Firstly, we check whether the length of the array is less than or equal to . If so, then the number of inversions is equal to .

Otherwise, we get and as the first and second halves of the array using the function that gets the subarray from (inclusive) to (exclusive).

Next, We add the number of inversions in and by calling recursively on both halves. Since both $\boldsymbol{L}$ and $\boldsymbol{R}$ become sorted, we can compute the number of inversions of the first type using the $\boldsymbol{CountInvOfFirstType}$ function.

After that, we merge the two sorted arrays into the array using merge function so that it becomes sorted as well. We assume that both functions countInv and merge take a reference to the array rather than taking a copy. Thus, when it gets edited inside the function, the edit will affect the original array.

4.3. Complexity

We note that the previous algorithm is very similar to the merge sort algorithm. The only difference is that we make another iteration on the elements of the array when we count the number of inversions of the first type (the first iteration was when we merged the two subarrays).

Therefore, the complexity is the same as the merge sort algorithm, which is $\boldsymbol{O(n \times log(n))}$ .

5. Usage

Suppose we have an array , and we want to find the minimum number of operations to get the array sorted. In one operation, we can swap any two adjacent elements.

The answer is the number of inversions. That’s because, in each operation, we decrease the number of inversions by $\boldsymbol{1}$ . When the array is sorted, the number of inversions will be equal to .

6. Conclusion

In this tutorial, we presented the problem of counting the number of inversions in an array. We explained the general idea and discussed two approaches for solving it. Also, we provided a fair usage of the discussed problem.

Persistence

REST

Security