算法细节系列（27）：时间复杂度为何还能优化？
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434790
算法细节系列（27）：时间复杂度为何还能优化？
详细代码可以fork下Github上leetcode项目，不定期更新。
以下题目非常有意思，乍一看它们的时间复杂度都是平方级的，但实际情况，却可以通过【动态数据结构】进行记忆优化降低时间复杂度，或者可以通过【分治手段】来降低时间复杂度。但为何复杂度就降低了？
题目摘自leetcode：
- Leetcode 315. Count of Smaller Numbers After Self
- Leetcode 327. Count of Range Sum
- Leetcode 493. Reverse Pairs
Leetcode 315. Count of Smaller Numbers After Self
Problem:
You are given an integer array nums and you have to return a new counts array. The counts array has the property where countsi is the number of smaller elements to the right of numsi.
Example 1:
Given nums = 5, 2, 6, 1 To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. Return the array 2, 1, 1, 0.
解法1
都知道一种O(n2)O(n^2)的解法，在当前位置i时，统计后续n-i个元素的大小关系，返回结果，非常简单，代码如下：
public List<Integer> countSmaller(int[] nums) {
List<Integer> count = new ArrayList<>();
for (int i = 0; i < nums.length; i++){
int cnt = 0;
for (int j = i + 1; j < nums.length; j++){
if (nums[j] < nums[i]) cnt ++;
}
count.add(cnt);
}
return count;
}TLE，原因：无记忆化，能否利用记忆化手段来降低时间复杂度？不急，先看看它的遍历结构。
起初，我是以这种方式来判断是否能优化复杂度，但这种形式化手段无助于理解这道题的本质。但同样可以给我一点思路，首先，5需要比较2，6，1，而2需要比较6，1，那就意味着比较6和1的信息是重复的，这点很关键，也是我们是否能进一步优化的重点。
这道题其实可以这么看：
这样，这些题目的结构就相当清楚了，5需要知道（2，6，1）的信息，而2需要知道（6，1）的信息，所以我们的一个优化方案是：
从小集合扩展到大集合，且在扩展的同时记录小集合的信息，看看是否能够扩展成大集合时用到小集合的信息，这样就避免了多次计算小集合。
时间复杂度能不下去么？
解法2
回到这道题，避免多次计算的手段基本手段是利用记忆化手段把信息记录到数组中，或者任何一种高级数据结构中去。所以这道题的优化思路是：
- 从右至左不断从小集合扩展至大集合。
- 这种动态的结构可以维护元素之间的关系（如：大小关系）。
- 当存在大小关系（有序数组），那么在搜索时，可以用二分查找来减少时间复杂度。
而恰巧，这道题从右至左不断扩展集合元素时，维护的就应该是大小关系，所以该题的具体操作如下：
- 从右至左遍历每个元素，遍历过的元素交给一个动态结构管理（维护有序性）。
- 每当遍历一个新元素时，便可以通过二分查找来确定比它小的左侧元素个数。
实现就交给代码，哈哈，有思路慢慢磨代码，总能出来。
public List<Integer> countSmaller(int[] nums) {
int len = nums.length;
Integer[] ans = new Integer[len];
List<Integer> sorted = new ArrayList<>();
for (int i = len - 1; i >= 0; i--){
int index = findIndex(sorted, nums[i]);
index = index == -1 ? 0 : index;
ans[i] = index;
sorted.add(index,nums[i]);
}
return Arrays.asList(ans);
}
private int findIndex(List<Integer> sorted, int target){
if (sorted.size() == 0) return 0;
int lf = 0, rt = sorted.size()-1;
while (lf < rt){
int mid = lf + (rt + 1 - lf) / 2;
if (sorted.get(mid) >= target){
rt = mid - 1;
}else{
lf = mid;
}
}
if (sorted.get(lf) < target) return lf+1;
return -1;
}这是二分手段，通过数组实现，但动态插入，ArrayList的时间复杂度为O(n)，虽然查找快，但插入慢。但实现二分查找还有一种更高级的数据结构，BST，树在实现插入和查找的时间复杂度均为O(logn)O(\log n)，所以可以进一步优化，看看BST如何去做。
解法3
同样的，BST的构建也是从右至左，而不是从左至右，神奇。基本思路差不多，把有序元素交给BST来维护，在插入和沉降的过程中，计算比它小的元素的个数。
如： nums = 3,2,2,6,1
插入顺序：1 6 2 2 3
括号中的含义：(sum, dup)
sum 表示比它小的元素的个数，如结点6，比它小的元素有2个2和1个3，所以有3个。
dup 表示重复元素，如2，有两。
所以当我们插入一个5时，它会从树根慢慢沉降到它该去的地方。
与此同时，边沉降边统计信息，如：
比较 1 和 5 的大小，把1中的个数(0 + 1)累加，分别表示比1小的个数和1本身。
比较 6 和 5 的大小，6比5大，所以修改结点6的信息，继续沉降。
比较 2 和 5 的大小，累加 (0 + 2).
比较 3 和 5 的大小，累加 (0 + 1).
插入完成，且比它小的个数在沉降过程中已计算完毕。
插入 7 试试它的过程。代码如下：
class BstTree{
BstTree left;
BstTree right;
int sum, val, dup = 1;
public BstTree(int sum, int val) {
this.sum = sum;
this.val = val;
}
@Override
public String toString() {
return "BstTree [val=" + val + "]";
}
}
private BstTree insert(int num, BstTree node, Integer[] ans, int i, int preSum){
if (node == null){
node = new BstTree(0,num);
ans[i] = preSum;
}else if (node.val == num){
node.dup++;
ans[i] = preSum + node.sum;
}else if (node.val > num){
node.sum++;
node.left = insert(num, node.left, ans, i, preSum);
}else{
node.right = insert(num, node.right, ans, i, preSum + node.sum + node.dup);
}
return node;
}
public List<Integer> countSmaller(int[] nums) {
Integer[] ans = new Integer[nums.length];
BstTree root = null;
for (int i = nums.length - 1; i >= 0; --i){
root = insert(nums[i], root, ans, i, 0);
}
return Arrays.asList(ans);
}在BST的插入实现上加些东西就好了。边沉降边计算，比较高级了。但BST它在最坏情况下，复杂度也为O(n2)O(n^2)，所以它还不是最完美的，能否用平衡二叉树？不行，平衡二叉树改变了插入元素的相对次序，而此题得严格按照从右至左的顺序依次插入。
解法4
考虑分治，逆序数用分治手段也能实现O(nlogn)O(n \log n)的复杂度，厉害厉害。考虑：
nums = 6 4 1 8 7 5 2 9这道题为什么能用分治？我也不知道为什么能用分治，但它的确是一种有效的手段，看看BST和分治解决这问题的视角对比：
分治的一个核心思想是分而治之，最后解能够合并它便是有效的。BST采用了信息记录的方式，在遍历所有元素的同时，不断维护有序性，从而降低时间复杂度。
来看看分治：
首先分治6，1的解一定是最终的解。但分治5，2的解一定不是最终解，因为它还需要6，1这一部分的信息。分治割裂它们的之间的关系，但最终在合并答案时，一定要有手段构造正确解。
如何构造正确解？
答：排序合并。因为我们知道了(5,2)和(6,1)的解，所以我们可以表示成：
5(2) 2(#) 括号内的元素表示比当前元素小的左侧元素，#表示空集
6(1) 1(#)
如何合并？排序！
2(#) 5(2)
1(#) 6(1)
开始merge
1(#)
因为1在(2,5)的左侧，所以不需要对它做任何处理
1(#) 2(1)
此时，2左侧的元素不再是空集，因为左侧有个1元素
1(#) 2(1) 5(2,1)
5左侧有元素1和之前的元素2
1(#) 2(1) 5(2,1) 6(1)
6元素不做任何操作同样地，时间复杂度之所以能够降低，是因为分治天然的记录了(6,1)的信息，并且在自底向上返回时，把信息交给了同一层的(5,2)，所以它快很多。或许还有另外一个重要的原因，它是一种强归纳手段，每次把集合划分成两部分处理，深度只有logn\log n。
代码如下：
public List<Integer> countSmaller(int[] nums) {
count = new int[nums.length];
int[] indexes = new int[nums.length];
for (int i = 0; i < nums.length; i++) indexes[i] = i;
mergeSort(nums, indexes, 0, nums.length-1);
List<Integer> ans = new ArrayList<>();
for (int i : count) ans.add(i);
return ans;
}
private void mergeSort(int[] nums, int[] indexes, int lo, int hi){
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
mergeSort(nums, indexes, lo, mid);
mergeSort(nums, indexes, mid+1, hi);
merge(nums, indexes, lo, hi);
}
int[] count;
private void merge(int[] nums, int[] indexes, int lo, int hi){
int mid = lo + (hi - lo) / 2;
int lf = lo;
int rt = mid + 1;
int[] aux = new int[hi - lo + 1];
int idx = 0;
int cnt = 0;
while (lf <= mid && rt <= hi){
int a1 = nums[indexes[lf]];
int a2 = nums[indexes[rt]];
if (a2 < a1){
aux[idx++] = indexes[rt++];
cnt++;
}else{
aux[idx++] = indexes[lf];
count[indexes[lf]] += cnt;
lf++;
}
}
while (lf <= mid){
aux[idx++] = indexes[lf];
count[indexes[lf]] += cnt;
lf++;
}
while (rt <= hi){
aux[idx++] = indexes[rt++];
}
for (int i = lo; i <= hi; i++){
indexes[i] = aux[i-lo];
}
}当然如果专注于问题性质的话，我们可以总结一句话：
当前元素的左侧元素是顺序无关的。
如：
nums = [5,1,2,3]
5: 1 2 3
5: 2 1 3
5: 3 2 1
....
这种形式都OK！答案对5没有影响，均为3
所以还不如寻找一种最优的结构来简化搜索，那么自然是1，2，3咯不瞎扯了，或许以后还会有其他的认识。
Leetcode 327. Count of Range Sum
Problem:
Given an integer array nums, return the number of range sums that lie in lower, upper inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
- A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = -2, 5, -1, lower = -2, upper = 2, Return 3. The three ranges are : 0, 0, 2, 2, 0, 2 and their respective sums are: -2, -1, 2.
有了前面一题的基础，用BST优化成O(nlogn)O(n\log n)不难。简单说说思路：
find:
lower <= sums[j] - sums[i] <= upper
转变：
a. sums[j] - lower >= sums[i] 已知j，求在左侧符合<=sums[i]的个数
b. sums[j] - upper <= sums[i] 已知j，求在左侧符合>=sums[i]的个数
求的是交集，所以条件b还可以进行转换，求：
c. sums[j] - upper > sums[i] 符合要求的个数
而ans = 条件a产生的个数 - 条件c产生的个数
条件a和条件b唯一的区别在于：对重复元素的计数此处把查询和insert分开是非常有趣的操作，这样可以假想一个val，去找寻符合条件的sumsi，简化了不少代码。
代码如下：
public int countRangeSum(int[] nums, int lower, int upper) {
if (nums == null || nums.length == 0) return 0;
int ans = 0;
long sum = 0;
Node root = new Node(0);
for (int i : nums){
sum += i;
ans += getBound(sum - lower, root, true) - getBound(sum - upper, root, false);
root = insert(root, sum);
}
return ans;
}
class Node{
long val;
int dup;
int small;
Node left;
Node right;
public Node(long val){
this.val = val;
dup = 1;
}
}
private int getBound(long val, Node root, boolean includeSelf){
if (root == null) return 0;
if (root.val == val) return root.small + (includeSelf ? root.dup : 0);
else if (root.val > val){
return getBound(val, root.left, includeSelf);
}else{
return root.small + root.dup + getBound(val, root.right, includeSelf);
}
}
private Node insert(Node root, long num){
if (root == null){
root = new Node(num);
}else if (root.val == num){
root.dup++;
}else if (root.val < num){
root.right = insert(root.right, num);
}else{
root.small++;
root.left = insert(root.left, num);
}
return root;
}还有一种分治的做法，代码量不多，但细节很烦人，技巧性比较强，代码如下：
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n + 1];
for (int i = 0; i < n; ++i)
sums[i + 1] = sums[i] + nums[i];
return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}
private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
if (end - start <= 1) return 0;
int mid = (start + end) / 2;
int count = countWhileMergeSort(sums, start, mid, lower, upper)
+ countWhileMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
for (int i = start, r = 0; i < mid; ++i, ++r) {
while (k < end && sums[k] - sums[i] < lower) k++;
while (j < end && sums[j] - sums[i] <= upper) j++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
count += j - k;
}
System.arraycopy(cache, 0, sums, start, t - start);
return count;
}其实在for循环中就做了两件事，一件是正常的归并操作，另外一件就是根据相同的sumsi求符合sumsk和sumsj的个数情况，和之前BST的操作类似，先查询后归并。
Leetcode 493. Reverse Pairs
一个道理，但使用BST超时了，可以采用分治归并。代码如下：
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if (s >= e) return 0;
int mid = s + (e - s) / 2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid + 1, e);
for (int i = s, j = mid + 1; i <= mid; ++i) {
while (j <= e && nums[i] / 2.0 > nums[j]) j++;
cnt += j - (mid + 1);
}
merge(nums, s, e);
return cnt;
}
private void merge(int[] nums, int s, int e){
int[] aux = new int[e - s + 1];
int mid = s + (e - s) / 2;
int i = s;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= e){
if (nums[i] < nums[j]) aux[k++] = nums[i++];
else aux[k++] = nums[j++];
}
while (i <= mid){
aux[k++] = nums[i++];
}
while (j <= e){
aux[k++] = nums[j++];
}
for (int l = 0; l < aux.length; ++l){
nums[l + s] = aux[l];
}
}