Given a list of integers nums, return the number of pairs i < j such that nums[i] > nums[j] * 3.
Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [7, 1, 2]
Output
2
Explanation
We have the pairs (7, 1) and (7, 2)
前置知识
二分法
暴力法（超时）
思路
暴力的解法可以枚举所有可能的 j，然后往前找 i 使得满足 $nums[i] > nums[j] * 3$，我们要做的就是将满足这种条件的 i 数出来有几个即可。这种算法时间复杂度为 $O(n^2)$。
代码
代码支持：Python3
Python3 Code:
class Solution:
def solve(self, A):
ans = 0
for i in range(len(A)):
for j in range(i+1,len(A)):
if A[i] > A[j] * 3: ans += 1
return ans
复杂度分析
令 n 为数组长度。
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
二分法
思路
这道题我们也可以反向思考。即思考：对于 nums 中的每一项 num，我们找前面出现过的大于 num * 3 的数。
我们可以自己构造有序序列 d，然后在 d 上做二分。如何构建 d 呢？很简单，就是将 nums 中已经遍历过的数字全部放到 d 中即可。
from sortedcontainers import SortedList
class Solution:
def solve(self, A):
d = SortedList()
ans = 0
for a in A:
i = d.bisect_right(a * 3)
ans += len(d) - i
d.add(a)
return ans
def mergeTwo(nums1, nums2):
res = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums[j]:
res.append(nums[i])
i += 1
else:
res.append(nums[j])
j += 1
while i < len(nums1) :
res.append(num[i])
i += 1
while j < len(nums1) :
res.append(num[j])
j += 1
return res
而我们要做的就是在上面的合并过程中统计逆序数。
为了方便描述，我将题目中的：i < j such that nums[i] > nums[j] * 3，改成 i < j such that nums[i] > nums[j]。也就是将 3 倍变成一倍。 如果你理解了这个过程，只需要比较的时候乘以 3 就行，其他逻辑不变。
