第六章 - 高频考题(困难)
Triple-Inversion

题目地址(762.Number Stream to Intervals)

题目描述

1
Given a list of integers nums, return the number of pairs i < j such that nums[i] > nums[j] * 3.
2
3
Constraints
4
5
n ≤ 100,000 where n is the length of nums
6
Example 1
7
Input
8
nums = [7, 1, 2]
9
Output
10
2
11
Explanation
12
We have the pairs (7, 1) and (7, 2)
Copied!

前置知识

  • 二分法

暴力法(超时)

思路

本题和力扣 493. 翻转对剑指 Offer 51. 数组中的逆序对 一样,都是求逆序对的换皮题。
暴力的解法可以枚举所有可能的 j,然后往前找 i 使得满足 $nums[i] > nums[j] * 3$,我们要做的就是将满足这种条件的 i 数出来有几个即可。这种算法时间复杂度为 $O(n^2)$。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def solve(self, A):
3
ans = 0
4
for i in range(len(A)):
5
for j in range(i+1,len(A)):
6
if A[i] > A[j] * 3: ans += 1
7
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(1)$

二分法

思路

这道题我们也可以反向思考。即思考:对于 nums 中的每一项 num,我们找前面出现过的大于 num * 3 的数。
我们可以自己构造有序序列 d,然后在 d 上做二分。如何构建 d 呢?很简单,就是将 nums 中已经遍历过的数字全部放到 d 中即可。
代码表示就是:
1
d = []
2
for a in A:
3
bisect.insort(d, a)
Copied!
bisect.insort 指的是使用二分找到插入点,并将数插入到数组中,使得插入后数组仍然有序。虽然使用了二分,使得找到插入点的时间复杂度为 $O(logn)$,但是由于数组的特性,插入导致的数组项后移的时间复杂度为 $O(n)$,因此总的时间复杂度为 $O(n^2)$。
Python3 Code:
1
class Solution:
2
def solve(self, A):
3
d = []
4
ans = 0
5
6
for a in A:
7
i = bisect.bisect_right(d, a * 3)
8
ans += len(d) - i
9
bisect.insort(d, a)
Copied!
由于上面的算法瓶颈在于数组的插入后移带来的时间。因此我们可以使用平衡二叉树来减少这部分时间,使用平衡二叉树可以使得插入时间稳定在 $O(logn)$,Python 可使用 SortedList 来实现, Java 可用 TreeMap 代替。

代码

代码支持:Python3
Python3 Code:
1
from sortedcontainers import SortedList
2
class Solution:
3
def solve(self, A):
4
d = SortedList()
5
ans = 0
6
7
for a in A:
8
i = d.bisect_right(a * 3)
9
ans += len(d) - i
10
d.add(a)
11
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$

分治法

思路

我们接下来介绍更广泛使用的,效率更高的解法 分治。 我们进行一次归并排序,并在归并过程中计算逆序数,换句话说 逆序对是归并排序的副产物
如果不熟悉归并排序,可以先查下相关资料。 如果你直接想看归并排序代码,那么将的代码统计 cnt 部分删除就好了。
归并排序实际上会把数组分成两个有序部分,我们不妨称其为左和右,归并排序的过程中会将左右两部分合并成一个有序的部分,对于每一个左右部分,我们分别计算其逆序数,然后全部加起来就是我们要求的逆序数。 那么分别如何求解左右部分的逆序数呢?
首先我们知道归并排序的核心在于合并,而合并两个有序数组是一个简单题目。 我这里给贴一下大概算法:
1
def mergeTwo(nums1, nums2):
2
res = []
3
i = j = 0
4
while i < len(nums1) and j < len(nums2):
5
if nums1[i] < nums[j]:
6
res.append(nums[i])
7
i += 1
8
else:
9
res.append(nums[j])
10
j += 1
11
while i < len(nums1) :
12
res.append(num[i])
13
i += 1
14
while j < len(nums1) :
15
res.append(num[j])
16
j += 1
17
return res
Copied!
而我们要做的就是在上面的合并过程中统计逆序数。
为了方便描述,我将题目中的:i < j such that nums[i] > nums[j] * 3,改成 i < j such that nums[i] > nums[j]。也就是将 3 倍变成一倍。 如果你理解了这个过程,只需要比较的时候乘以 3 就行,其他逻辑不变。
️ 比如对于左:[1,2,3,4]右:[2,5]。由于我的算法是按照 [start, mid], [mid, end] 区间分割的,因此这里的 mid 为 3(具体可参考下方代码区)。 其中 ij 指针如粗体部分(左数组的 3 和右数组的 2)。 那么 逆序数就是 mid - i + 1 也就是 3 - 2 + 1 = 2(3,2)(4,2)。 其原因在于如果 3 大于 2,那么 3 后面不用看了,肯定都大于 2。 ️ 之后会变成:[1,2,3,4] 右:[2,5] (左数组的 3 和 右数组的 5),继续按照上面的方法计算直到无法进行即可。
1
class Solution:
2
def solve(self, nums: List[int]) -> int:
3
self.cnt = 0
4
def merge(nums, start, mid, end):
5
i, j, temp = start, mid + 1, []
6
while i <= mid and j <= end:
7
if nums[i] <= nums[j]:
8
temp.append(nums[i])
9
i += 1
10
else:
11
self.cnt += mid - i + 1
12
temp.append(nums[j])
13
j += 1
14
while i <= mid:
15
temp.append(nums[i])
16
i += 1
17
while j <= end:
18
temp.append(nums[j])
19
j += 1
20
21
for i in range(len(temp)):
22
nums[start + i] = temp[i]
23
24
25
def mergeSort(nums, start, end):
26
if start >= end: return
27
mid = (start + end) >> 1
28
mergeSort(nums, start, mid)
29
mergeSort(nums, mid + 1, end)
30
merge(nums, start, mid, end)
31
mergeSort(nums, 0, len(nums) - 1)
32
return self.cnt
Copied!
注意上述算法在 mergeSort 中我们每次都开辟一个新的 temp,这样空间复杂度大概相当于 NlogN,实际上我们完全每必要每次 mergeSort 都开辟一个新的,而是大家也都用一个。具体见下方代码区。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def solve(self, nums) -> int:
3
self.cnt = 0
4
def merge(nums, start, mid, end, temp):
5
i, j = start, mid + 1
6
while i <= mid and j <= end:
7
if nums[i] <= nums[j]:
8
temp.append(nums[i])
9
i += 1
10
else:
11
temp.append(nums[j])
12
j += 1
13
# 防住
14
# 这里代码开始
15
ti, tj = start, mid + 1
16
while ti <= mid and tj <= end:
17
if nums[ti] <= 3 * nums[tj]:
18
ti += 1
19
else:
20
self.cnt += mid - ti + 1
21
tj += 1
22
# 这里代码结束
23
while i <= mid:
24
temp.append(nums[i])
25
i += 1
26
while j <= end:
27
temp.append(nums[j])
28
j += 1
29
for i in range(len(temp)):
30
nums[start + i] = temp[i]
31
temp.clear()
32
33
34
def mergeSort(nums, start, end, temp):
35
if start >= end: return
36
mid = (start + end) >> 1
37
mergeSort(nums, start, mid, temp)
38
mergeSort(nums, mid + 1, end, temp)
39
merge(nums, start, mid, end, temp)
40
mergeSort(nums, 0, len(nums) - 1, [])
41
return self.cnt
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。