目录

Leetcode 493 翻转对

目录

想把这题记录下来的原因,主要是题解的归并算法思路比较典型,所以希望能够记住并掌握这种方法。

题目要求对一个数组进行处理,计算出所有满足nums[i] > 2*nums[j]i < j(i, j)对的个数。测试用例中最长数组长度为50000。那很显然,不能两次遍历,因为O(n^2)肯定会超时的。所以需要寻求其他方法。

再次思考要求,ij的前后顺序是确定的,而且又是处理数组,并且要求低于O(n^2)的复杂度,所以应该想到归并排序(当然现在的我是上帝视角🤣)。

归并排序的过程中,每次合并两个已经排好序的数组时,对于固定前后顺序的下标处理就会变得简单许多了。

在实现的时候,还可以继续对处理过程进行部分优化,python3实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from typing import List
import time
import random

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        '''
        这样就不超时了
        但是还是很慢🙄
        '''
        def countPairs(left: int, mid: int, right: int) -> int:
            res = 0
            lastj = mid + 1
            # 由于左右两边是已经排好序的,所以这里可以优化,对第一个之后的i,j并不需要从头开始遍历
            for i in range(left, mid + 1):
                while lastj <= right and nums[i] > 2 * nums[lastj]:
                    lastj += 1
                res += lastj - (mid + 1)
            return res
        
        def mergeAndCount(left: int, right: int) -> int:
            if left == right: return 0
            mid = (left + right) // 2
            res = mergeAndCount(left, mid) + mergeAndCount(mid + 1, right) + countPairs(left, mid, right)
            i,j,k = left, mid+1, left
            while i < mid+1 and j < right+1:
                if nums[i] < nums[j]: 
                    sortedNums[k] = nums[i]
                    i += 1
                else:
                    sortedNums[k] = nums[j]
                    j += 1
                k += 1
            
            while i < mid+1:
                sortedNums[k] = nums[i]
                i += 1
                k += 1

            while j < right+1:
                sortedNums[k] = nums[j]
                j += 1
                k += 1
            
            for t in range(left, right+1):
                nums[t] = sortedNums[t]
            
            return res

        if not nums:
            return 0
        sortedNums = [0 for i in range(len(nums))]
        return mergeAndCount(0, len(nums)-1)
                
if __name__ == "__main__":
    s = Solution()
    nums = [1, 26, 20, 66, 28, 75, 78, 15, 40, 64]
    # random.seed(time.time())
    # for i in range(10):
    #     nums.append(random.randrange(1,100))
    print(nums)
    print(s.reversePairs(nums))
    print(nums)
            

327题同样也用到了这个思想,博客记录在这