[剑指Offer] 51_数组中的逆序对

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

例：

在数组中{7, 5, 6, 4}中，一共存在5个逆序对，分别是(7, 6)、(7, 5)、(7, 4)、(6, 4)、(5, 4)

---

思路

1. 顺序扫描整个数组，向后比较是否存在逆序对。
   1. 时间复杂度：O(n^2)
   2. 空间复杂度：O(1)
2. 分析逆序对多少就是将数组从小到大排序需要和前面的元素交换的次数。因此逆序对就等于冒泡排序交换的次数。为了减小时间复杂度，可以采用归并排序，可以看到在merge的过程中【交换1次】等于有【右侧子数组剩下的数字个数】个逆序对。
   1. 时间复杂度：O(nlgon)
   2. 空间复杂度：O(n)辅助空间

---

代码

思路2：时间复杂度：O(nlgon)，空间复杂度：O(n)

def inverse_pairs(array):
    """
    :param array:array
    :return: number of inverse pairs
    """
    def merge_sort(nums, left, right):
        """
        :param nums:total array
        :param left: left index
        :param right: right index
        :return: sorted array
        """
        def merge(left, right):
            """
            :param left:left subarray
            :param right:right subarray
            :return:sorted array
            """
            nonlocal inverse
            i, j = len(left) - 1, len(right) - 1
            k = i + j + 1
            sorted = [0] * (k+1)
            while i >= 0 and j >= 0:
                if left[i] <= right[j]:
                    # sorted =  [right[j]] + sorted
                    sorted[k] = right[j]
                    j -= 1
                else:
                    # sorted = [left[i]] + sorted
                    sorted[k] = right[i]
                    inverse += j+1
                    i -= 1
                k -= 1
            # sorted = left[:i+1] + sorted
            # sorted = right[:j+1] + sorted
            sorted[:k+1] = left[:i+1] or right[:j+1]
            return sorted

        mid = (left + right) // 2
        if right - left <= 1:
            return nums[left:right]
        left = merge_sort(array, left, mid)
        right = merge_sort(array, mid, right)
        return merge(left, right)

    inverse = 0
    merge_sort(array, 0, len(array))

    return inverse

---

思考

用归并排序减小了时间复杂度，但是空间复杂度也增加了，有没有使用O(1)空间复杂度的办法。