leetcode 315

题目

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
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.

判断数组某个元素右边有几个比他小的

思路

Brute force

最容易想到的:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        count = [0]*len(nums)
        for i in range(len(nums)):
            for j in range(len(nums))[i+1:]: 
                if nums[j]<nums[i]:
                    count[i] +=1
        return count

时间复杂度O(n2)太大.

1 2	Time Limit Exceeded 15/16 cases passed (N/A)

Fenwick Tree/ Binary Indexed Tree(BST)

逆序

归并排序

以[5, 2, 6, 1]为例，我们使用归并排序解决这个问题：
首先归并排序将[5, 2, 6, 1]分为

[5, 2], [6, 1]

然后因为再归并的话可以得到

[[5], [2]], [[6], [1]]

在[[5], [2]]中，[2]位于整个区间的右部，所以结果为0；[5]位于左边，使[5]中每个元素都与右边[2]比较，可以得到5的count值为1；比较完成后对[[5], [2]]进行排序，得到：

[[5(1)], [2]], [[1], [6]]

然后在[[1], [6]]中执行相同的操作，1的count值为0， 6的count值为1，得到：

[[2], [5(1)]], [[1], [6(1)]]

然后在[[[2], [5(1)]], [[1], [6(1)]]]中进行比较，左边[[2], [5(1)]]中每个数值都在[[1], [6(1)]]进行遍历计数，由于[[1], [6(1)]]和[[2], [5(1)]]都已经排好序了，所以只需要遍历一遍就可以得到结果：

[[2(1)], [5(2)]], [[1], [6(1)]]

每次通过辅助的拷贝数组将计数信息保存到正确的位置即可；
由于使用了归并排序，所以每次进行比较的时候都是比较的有序队列，这样可以很好地提高效率，同时也保证了每一轮次左右相对位置的稳定；

代码

def countSmaller(nums):
    def sort(enum):
        half = int(len(enum) / 2)
        if half:
            left, right = sort(enum[:half]), sort(enum[half:])
            for i in range(len(enum))[::-1]:
                print(i)
                # left[-1][1]: 左边最后一个元素的值,right[-1][1]: 右边最后一个元素的值
                # 由于子序列是有序的，左边元素最小，右边元素最大
                print("left:", left)
                print("right:", right)
                # 因为不停弹出数据，所以left，right有可能为空的情况
                if not right or left and left[-1][1] > right[-1][1]:
                    # 使用pop，每次弹出最后一个元素
                    smaller[left[-1][0]] += len(right)
                    enum[i] = left.pop()
                else:
                    enum[i] = right.pop()
        print("enum", enum)
        print("smaller:", smaller)
        print("=============")
        return enum

    smaller = [0] * len(nums)
    # 虽然数组有序的，但是原始顺序变化了,计算每个元素数量需要找到他们的位置，因此需要记录每个元素的index
    sort(list(enumerate(nums)))
    return smaller


if __name__ == '__main__':
    nums = [5, 2, 6, 1]
    print("input:", nums)
    smaller = countSmaller(nums)
    print("output:", smaller)

题目

思路

Brute force

Fenwick Tree/ Binary Indexed Tree(BST)

归并排序

代码

参考文档