Topic describes

Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions in the array.

Example 1: input: [7,5,6,4] output: 5

1. Brute force Cracking (timeout)

Brute force method, we directly from the back to the front of the number of double traversal, to see if the following element is less than the preceding element, count+1. Once you’re done iterating, you can get the data. Because it’s O(n^2), it’s going to time out

Example code 1:

def reversePairs2(self, nums: [int]) - >int:
    res = 0
    l = len(nums) - 1
    for i in range(0, l + 1) :for j in range(i + 1, l + 1) :print(nums[l - i], nums[l - j])
            if nums[l - i] < nums[l - j]:
                res += 1

    return res
Copy the code

2. Merge sort

  1. Because merge sort will first divide the array into left and right parts for recursion, using the idea of merge sort, when merging after the completion of divide and conquer, it is to merge the left and right two ordered arrays into a new ordered array. In this merging process we can reverse the calculation
  2. When A element in the left array (the first element) is greater than B element in the right array (the second element), since both arrays are ordered, all elements after A are greater than B element, then we have the left array A and the N elements after A and B elements in reverse order
  3. According to Step 2, we keep counting through the merge, and we end up with all the inversions

Example code 2:

def reversePairs(self, nums: [int]) - >int:

    def mergeSort(arr) :
        if len(arr) <= 1:
            return arr
        else:
            mid = int(len(arr) / 2)
            left = mergeSort(arr[:mid])
            right = mergeSort(arr[mid:])
            return merge(left, right)

    def merge(left, right) :
        result = []
        i = 0
        j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                # Step 2: Determine inversions during the merge process
                self.count += len(left) - i
                result.append(right[j])
                j += 1

        result += left[i:]
        result += right[j:]
        return result

    self.count = 0
    mergeSort(nums)
    return self.count
Copy the code