逆序对数

2019/04/04 20:55
阅读数 20

题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

解题思路:

我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候,我们不拿ta和后面的每一个数字作比较,否则时间复杂度就是O(n^2),因此我们可以考虑先比较两个相邻的数字。

(a) 把长度为4的数组分解成两个长度为2的子数组;
(b) 把长度为2的数组分解成两个成都为1的子数组;
(c) 把长度为1的子数组 合并、排序并统计逆序对 ;
(d) 把长度为2的子数组合并、排序,并统计逆序对;
在上图(a)和(b)中,我们先把数组分解成两个长度为2的子数组,再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组,一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5,因此(7,5)组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对(6,4)。由于我们已经统计了这两对子数组内部的逆序对,因此需要把这两对子数组 排序 如上图(c)所示, 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾,并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字,则构成逆序对,并且逆序对的数目等于第二个子数组中剩余数字的个数,如下图(a)和(c)所示。如果第一个数组的数字小于或等于第二个数组中的数字,则不构成逆序对,如图b所示。每一次比较的时候,我们都把较大的数字从后面往前复制到一个辅助数组中,确保 辅助数组(记为copy) 中的数字是递增排序的。在把较大的数字复制到辅助数组之后,把对应的指针向前移动一位,接下来进行下一轮比较。
 
过程:先把数组分割成子数组,先统计出子数组内部的逆序对的数目,然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中,还需要对数组进行排序。如果对排序算法很熟悉,我们不难发现这个过程实际上就是归并排序。参考代码如下:
class Solution:
    def InversePairs(self, data):
        # write code here
        return self.inverseCount(data[:], 0, len(data)-1, data[:])%1000000007
       
    def inverseCount(self, tmp, start, end, data):
        if end-start <1:
            return 0
        if end - start == 1:
            if data[start]<=data[end]:
                return 0
            else:
                tmp[start], tmp[end] = data[end], data[start]
                return 1
        mid = (start+end)//2
        cnt = self.inverseCount(data, start, mid, tmp) + self.inverseCount(data, mid+1, end, tmp)
        # print(start, mid, end, cnt, data)
        i = start
        j = mid + 1
        ind = start
           
        while(i <= mid and j <= end):
            if data[i] <= data[j]:
                tmp[ind] = data[i]
                i += 1
            else:
                tmp[ind] = data[j]
                cnt += mid - i + 1
                j += 1
            ind += 1
        while(i<=mid):
            tmp[ind] = data[i]
            i += 1
            ind += 1
        while(j<=end):
            tmp[ind] = data[j]
            j += 1
            ind += 1
        return cnt

还有一个更简洁的方法,时间复杂度也是nlogn

先将原序列排序,然后从排完序的数组中取出最小的,它在原数组中的位置表示有多少比它大的数在它前面,每取出一个在原数组中删除该元素,保证后面取出的元素在原数组中是最小的,这样其位置才能表示有多少比它大的数在它前面,即逆序对数。

代码如下:

class Solution:
    def InversePairs(self, data):
        count = 0
        copy = []
        for i in data:
            copy.append(i)
        copy.sort()
        for i in range(len(copy)):
            count += data.index(copy[i])
            data.remove(copy[i])
        return count%1000000007

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部