---

3-3 排序相关题目

---

版权声明：以下题目均来自 LeetCode， 仅仅提供跳转到力扣官网的链接，不在本页面出现题目内容，本文章内容禁止商业用途。

目录

序号	题目	题解
①	LeetCode 912.排序数组	3.3.1题解
②	LCR 164. 破解闯关密码	3.3.2题解
③	LeetCode 179.最大数	3.3.3题解
④	LeetCode 283.移动零	3.3.4题解
⑤	LeetCode 75.颜色分类	3.3.5题解
⑥	LeetCode 217.存在重复元素	3.3.6题解
⑦	LeetCode 219. 存在重复元素II	3.3.7题解
⑧	LeetCode 220.存在重复元素 III	3.3.8题解
⑨	LeetCode 164.最大间距	3.3.9题解
⑩	LeetCode 215.数组中的第K个最大元素	3.3.10题解
⑪	LeetCode 剑指 Offer 40.最小的k个数	3.3.11题解
⑫	LeetCode 169.多数元素	3.3.12题解
⑬	LeetCode 88.合并两个有序数组	3.3.13题解
⑭	LCR 170. 交易逆序对的总数	3.3.14题解
⑮	LeetCode 315.计算右侧小于当前元素的个数	3.3.15题解
⑯	LeetCode 973.最接近原点的 K 个点	3.3.16题解

3.3.1 排序数组

LeetCode 912.排序数组 | | 返回目录3.3

思路：这个题就是简单的考察排序算法，可以用这个题来当作测试模板，看看自己写的各个版本的排序代码是不是正确的。
但是一般在做题是很少会用到时间复杂度 O(n^2)的算法，一般都是用的 O(N*logN) 的算法，或者视具体情况使用计数排序、基数排序、桶排序。

# 具体的排序算法 code 可以看 文章3-1 中的详细简介，这里就不写了

3.3.2 把数组排成最小的数

LCR 164. 破解闯关密码 | | 返回目录3.3

思路：这个题就其实比较新奇，是考察排序，但是排序的规则不是按照我们平时的数值大小。
针对此题，我们对字符串 x, y 的大小 作如下 自定义：
如果：x + y > y + x , 则 x > y;
如果：x + y == y + x , 则 x = y;
如果：x + y < y + x , 则 x < y;
按照我们自定义的规则进行排序即可，题目要求是最小的数，那么就按照降序排列。

同时，题目中叙述 “最后结果不需要去掉前导 0”，意思是如果出现 [1,2,0] 这样的数组，结果可以输出 “012” 这样的字符串。

class Solution:
    def minNumber(self, nums: List[int]) -> str:

        def comp_str(x:str,y:str)->int:
            '''
            definition:
            if x+y > y+x: x>y
            elif x+y == y+x: x==y
            else: x<y
            '''
            if x+y > y+x:
                return 3
            elif x+y == y+x:
                return 2
            else:
                return 1

        def QuickSort(a, L, R):
            if L >= R:
                return
            
            pl, pr, key = L-1, R, R 
            i = pl+1
            while i < pr:
                # 利用自定义的大小规则，进行快速排序的大小比对
                comp = comp_str(a[i], a[key])
                if comp == 1:
                    a[i], a[pl+1] = a[pl+1], a[i]
                    pl += 1
                    i += 1
                elif comp == 2:
                    i += 1
                else:
                    a[i], a[pr-1] = a[pr-1], a[i]
                    pr -= 1
            # i==pr 
            a[pr], a[key] = a[key], a[pr]
            QuickSort(a,L, pl)
            QuickSort(a, pr+1, R)
            return 
        # 将数字转化为字符串
        str_list = list(map(str,nums))
        QuickSort(str_list, 0, len(str_list)-1)
        
        return ''.join(str_list)

3.3.3 最大数

LeetCode 179.最大数 | | 返回目录3.3

思路：这个题和上一个题其实是一回事，只不过一个要最小数，一个要最大数。所以这个题需要按自定义规则从大到小排序即可。。

但要注意的是，由于此题是要求排列最大的情况，所以如果有单个0和其他整数出现，0必不会出现在开头，而是会出现在末尾。
只有一种特殊情况，那就是数组中只有0的时候，比如[0,0,0]，字符串的结果是 “000”，我们需要处理成对应的整数形式 “0”

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def comp_str(x:str,y:str)->int:
            '''
            definition:
            if x+y > y+x: x>y
            elif x+y == y+x: x==y
            else: x<y
            '''
            if x+y > y+x:
                return 1
            elif x+y == y+x:
                return 2
            else:
                return 3

        def QuickSort(a, L, R):
            if L >= R:
                return
            
            pl, pr, key = L-1, R, R 
            i = pl+1
            while i < pr:
                comp = comp_str(a[i], a[key])
                if comp == 1:
                    a[i], a[pl+1] = a[pl+1], a[i]
                    pl += 1
                    i += 1
                elif comp == 2:
                    i += 1
                else:
                    a[i], a[pr-1] = a[pr-1], a[i]
                    pr -= 1
            # i==pr 
            a[pr], a[key] = a[key], a[pr]
            QuickSort(a,L, pl)
            QuickSort(a, pr+1, R)
            return 

        str_list = list(map(str,nums))
        QuickSort(str_list, 0, len(str_list)-1)
        
        s = ''.join(str_list)
        # 这个题的要求没有说可以不处理先导 0
        # 所以如果出现了"000"这种情况，要手动处理成 '0'
        if int(s) == 0:
            return '0'
        else:
            return s

3.3.4 移动零

LeetCode 283.移动零 | | 返回目录3.3

思路：这个提已经在 2-3 数组双指针 中的 2.3.2.5 讲解过，在3-2快速排序讨论中时，介绍的partition问题也对其进行深入讨论过。
按照partition问题的理解，就是与0比较，非0数排左侧，0排右侧。
需要注意的是，Partition 操作本身是不稳定移动，（这也是快速排序是不稳定排序的原因）但是应用到该题中，只有0的部分会不稳定，（即几个0之间可能发生相对位置的变化）而非0部分的相对顺序是不会变的。是符合题目要求的。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        N = len(nums)
        ps, pf = -1, 0
        while pf <N:
            if nums[pf] != 0:
                nums[pf], nums[ps+1] = nums[ps+1], nums[pf]
                ps += 1
            pf += 1

3.3.5 颜色分类

LeetCode 75.颜色分类 | | 返回目录3.3

思路：在3-2快速排序讨论中讨论过的荷兰国旗问题。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        '''荷兰国旗问题'''
        N = len(nums)
        L, R = -1, N
        i = L+1
        while i < R:
            if L < R and nums[i] < 1:
                nums[i], nums[L+1] = nums[L+1], nums[i]
                L+=1
                i+=1
            elif L < R and nums[i] == 1:
                i+=1
            else:
                nums[i], nums[R-1] = nums[R-1], nums[i]
                R -=1

3.3.6 存在重复元素

LeetCode 217.存在重复元素 | | 返回目录3.3

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

思路：较为简单，使用哈希表计数即可。
这个题主要是为了下面两个题做铺垫。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        h = dict()
        for i in range(len(nums)):
            if nums[i] not in h:
                h[nums[i]] = 1
            else:
                return True
        return False

3.3.7 存在重复元素II

LeetCode 219. 存在重复元素II | | 返回目录3.3

思路1：这个题也可以理解为找寻找至少出现两次的元素，只不过多了一个条件，即两数索引之间的距离不能超过 k。
简单的思路是：用哈希表存储数字的索引，计算重复出现的数字的索引之差，满足条件则可以返回True；
否则就用最新的索引 i 进行覆盖，以方便下一次判断条件。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        h = dict()
        N =len(nums)
        for i in range(N):
            if nums[i] in h and i-h[nums[i]] <=k :
                # 如果哈希表中已经存在该数, 且索引之差 <=k
                return True 
            else:
                # 用最新的索引 i 覆盖
                h[nums[i]] = i
        return False

思路 2：还有一种方案，那就是 每次遍历到 i 时，将哈希表中，前 k 个位置 之前的元素 删除掉。如果是在最近的 k 个数范围内，就不删除。
即哈希表中只保留距离i最近的k个数，这样就不需要去计算是否符合索引值差小于等于k，因为只要没被删除的，就一定在 最近的 k 个范围。
该思路的时间消耗比思路1长，但是空间消耗比思路1小。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        h = dict()
        N =len(nums)
        for i in range(N):
            if i > k: # 说明目前遍历的已经超过了 k 个数
                # 且仍未返回True
                # 那么直接删除 距离当前 i 超过 k 的元素对应的键值对
                # 即哈希表中只保留距离i最近的k个数
                h.pop(nums[i-(k+1)])
            
            if nums[i] in h:
                # 哈希表中已存在该数, 说明是第二次出现了
                return True
            else:
                h[nums[i]] = i

        return False

3.3.8 存在重复元素 III

LeetCode 220.存在重复元素 III | | 返回目录3.3

思路1：遍历数组，每次遍历时，在大小为 indexDiff 区间上进行遍历，看看是否有符合条件的数字。
这种思路比较直观，容易想到，能跑通大部分用例；但是对于某一些用例，会出现超时现象。
因为时间复杂度是O(N*indexDiff)

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        N =len(nums)
        k = indexDiff
        for i in range(1, N):
            # 对于数组的每一个数字，都在它前方的 indexDiff 区间对比数值
            for j in range(max(0,i-k),i):
                if abs(nums[i] - nums[j]) <= valueDiff:
                    return True
        return False

思路2：所以如何能高效判断 abs(nums[i] - nums[j]) <= valueDiff ？ 是该题的要点。

• 上面两个题，是要判断【两个数字在重复出现】的情况下，索引的差值是否满足条件。
  那么这里如果将元素按照值域进行分组呢？满足条件的数落到同一个分桶里。那么问题就转化为：
  两个数字在重复出现在一个分桶，即【两个数字的分桶序号重复出现】的情况下，索引的差值是否满足条件。
  然后思路就是一样的了。

• 所以先对数字进行分桶操作：设 t = valueDiff
  取最差的情况，即两个数相差 t，比如 0 和 t, 那么可见每个分桶内应该有(t+1)个元素，那么我们就每隔(t+1)的值进行分桶，即看数字是 (t+1) 的多少倍，就分入哪个桶。

• 另外，如果两个数落在不同分桶，也不是说就一定不满足情况，比如 若a=t 和 b=t+1按照我们上面的分桶规则，就会分别分入0号桶和1号桶，但是他们也是有可能满足索引差值的条件的。所以还需考察相邻的桶的元素。

• 还有，这里说的对数字进行分桶，并不是先对全部数字分好桶，而是一边遍历，一边对数字进行分桶；参考上两个题在遍历时对数字存入hash表，这里也是在遍历时分桶，然后将分桶的序号存入哈希表。也就是说其实这里分桶只是在虚拟分桶，只会用到桶的序号。

写法一：参考上一题目3.3.7的思路1的代码写法

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        h = dict()
        N =len(nums)
        t, k = valueDiff, indexDiff
        for i in range(N):
            # 先计算当前数字的分桶序号 group_idx
            group_idx = nums[i] // (t + 1)
            if group_idx in h and i-h[group_idx] <=k :
                # 如果哈希表中已存在该序号，说明两数之差 <=t
                # 且索引之差也<=k
                return True 

            # 要考虑左右相邻两个桶内是否也有符合条件的数            
            elif group_idx-1 in h and abs(i-h[group_idx-1]) <= k and abs(nums[i]-nums[h[group_idx-1]]) <=t :
            # # 如果1.左桶存在； and 2.数字序号之差 <=k; and 3.数值之差<=t
                return True
            elif group_idx+1 in h and abs(i-h[group_idx+1]) <= k and abs(nums[i]-nums[h[group_idx+1]]) <=t :
            # # 如果1.右桶存在； and 2.数字序号之差 <=k; and 3.数值之差<=t
                return True

            else:
                # 用最新的索引 i 覆盖 
                h[group_idx] = i
        return False   

写法二：参考上一题目3.3.7的思路2的代码写法

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        '''因为哈希表只存储最近的k个数，所以比上面的代码要节省空间'''
        group = dict()
        N = len(nums)
        t, k = valueDiff, indexDiff
        for i in range(N):
            # 即哈希表中只保留距离i最近的k个数
            if i > k:
                # 计算更前面的数字的分桶序号, 并将其从哈希表中移除
                old_key = nums[i - (k+1)] // (t + 1)
                group.pop(old_key)
            # 经过这个if条件，各个桶中如果仍存在元素，则必然满足 abs(i-j)<=k这个条件
            # 下面只需要考察 abs(nums[i] - nums[j]) <= t 这个条件即可

            # 计算当前i位置数字的分桶序号
            key = nums[i] // (t + 1)

            if key in group:
                # 哈希表中已存在该分桶序号，说明这两个数被分入同一个桶
                # 即 abs(nums[i] - nums[j]) <= t 满足
                return True

            # 判断左右侧桶是否满足条件
            # 这里注意到，因为哈希表中只保留了距离i最近的k个数，所以这里相较于上面的代码
            # 可以不用比较索引是否满足条件，因为一定满足条件
            # 只需要比较数值之差是否满足条件
            elif (key - 1) in group and abs(nums[group[key - 1]] - nums[i]) <= t:
                return True
            # 判断右侧桶是否满足条件
            elif (key + 1) in group and abs(nums[group[key + 1]] - nums[i]) <= t:
                return True

            else:
                # 用最新的索引 i 覆盖 
                group[key] = i

        return False

3.3.9 最大间距

LeetCode 164.最大间距 | | 返回目录3.3

思路：此题要求 时间复杂度是 O(N), 空间复杂度也是O(N)
已经在暗示要从计数排序、基数排序、桶排序中找方法做了。
该题数字的范围看起来要比数字规模大(0 <= nums[i] <= 10^9; 1 <= nums.length <= 10^5)，计数排序可能没有桶排序表现好，我这里使用桶排序。

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        N = len(nums)
        if N < 2:
            return 0
        
        '''最基础的情况，元素都为非负整数'''
        max_v = max(nums)
        # d 这里在统计最高的位数
        d = len(str(max_v))

        for i in range(d):
            radix = 10 ** i # radix 代表本次循环基于哪一个位
            Groups = [[] for _ in range(10)] # 初始化从0到9，共10个分组

            for num in nums:
                digit = num // radix % 10
                # 按照当前位的数字，将原始数据分别装入不同的group中
                Groups[digit].append(num)

            # 该 print 函数能打印各个阶段 数字装入分组后的状况，
            # 可以取消注释后打印中间结果，帮助理解
            # print(i, Groups)        
            j = 0
            for group in Groups:
                for num in group:
                    nums[j] = num 
                    j += 1
        print(nums)
        max_res = 0
        for m in range(1,N):
            max_res = max(max_res, abs(nums[m-1]-nums[m]))
            # print(max_res)
        
        return max_res

3.3.10 数组中的第K个最大元素

LeetCode 215.数组中的第K个最大元素 | | 返回目录3.3

思路 1：题目中又出现了 【时间复杂度为 O(n)】，又可以考虑计数排序、基数排序、桶排序。
计数排序 O(n+width),该题 n 最大为 10^5; width最大为 2*10^4:
即最大的 n > 最大的 width，所以可以先用计数排序尝试一次

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        '''题目条件中可能出现负数，所以要用delta做偏移'''
        def CountSort_update(a, K):
            max_v, min_v = max(a), min(a)
            # max、min 函数的时间复杂度是 O(n)，符合题意

            delta = -min(0, min_v)
            # 空间复杂度 O(width)
            count_list = [0]*(1+max_v+delta)
            # 遍历数组a，时间负责度 O(n)
            for num in a:
                count_list[num+delta] +=1
            
            i = 0
            # 注意，由于题目中要求的是 第 k 大的数
            # 我们此时从后往前取，就是从大的那边开始取，取够k个就停止
            # 所以该循环时间复杂度是O(k), k最大也就只能是n, 不会超过数组本身规模
            # (极端情况，第 n 大的数, 也就是数组中最小的数)
            for elem in range(max_v+delta, -1, -1):
                while count_list[elem] > 0:
                    # a[i] = elem - delta
                    # i 是从0开始的，所以 i == k-1时，就是第 k 个数
                    if i == K-1:
                        return elem - delta
                    count_list[elem] -= 1
                    i += 1
        # 综上所述, 时间复杂度依然是O(n)，符合题意
        return CountSort_update(nums,k)

思路 2： 由于数字最多只有5位： -10000 or 10000；
更多的情况只有 4 位，所以基数排序的时间复杂度 O(nd) = O(5n) = O(n),也值得一试。
只不过要注意这里会有负数，所以处理上要稍微仔细一点。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        '''简单基数排序也能跑通所有样例'''
        def RadixSort(nums):
            max_v, min_v = max(nums), min(nums)
            # 因为可能存在负数，所以要排除负号
            d1 = len(str(max_v)) if max_v > 0 else len(str(max_v)) -1
            d2 = len(str(min_v)) if min_v > 0 else len(str(min_v)) -1
            d = max(d1, d2)

            for i in range(d):
                radix = 10**i
                Groups = [ [] for _ in range(10)]
                Groups_neg = [ [] for _ in range(10)]
                # Groups_neg: [0:-9], [1:-8], [8:-1], [9:-0]
                
                for num in nums:
                    digit = int(num/radix) % 10 
                    if num > 0:
                        Groups[digit].append(num)
                    else:
                        Groups_neg[digit-1].append(num) 

                j = 0
                for group in Groups_neg:
                    for num in group:
                        nums[j] = num 
                        j+=1

                for group in Groups:
                    for num in group:
                        nums[j] = num 
                        j+=1
            return 
        
        RadixSort(nums)
        # 因为我们是从小到大排序的，所以这里取数时要注意换算
        return nums[len(nums) - k]

思路 3： 使用堆排序。虽然完整的堆排序，时间复杂度是 O(NlogN);
但是我们并不需要使用完整的堆排序，先构造大根堆,时间复杂度O(N)；
再进行 k-1次 heapify恢复大根堆操作，时间复杂度 kO(logN);
总时间复杂度 O(N) + kO(logN) 约为 O(N), 也可以尝试一下

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def Heapify(a, index, heapsize):
            '''时间复杂度 o(logN) '''
            L = 2*index+1
            while L <= heapsize:
                R = L+1
                large = R if(R<=heapsize and a[R] > a[L]) else L
                large = large if a[large] > a[index] else index
                if large == index :
                    break
                a[index], a[large] = a[large], a[index]
                index = large 
                L = 2*index+1
        
        N = len(nums)
        '''构造大根堆 时间复杂度 o(N) '''
        for i in range(int(N/2), -1, -1):
            Heapify(nums, i, N-1)
        
        # small = min(nums)-1
        small = -10001 
        # 用更小的数替换掉大根堆堆顶, 相当与将这个最大数给删除了，因为我们本来就不需要它
        # k*O(logN) = O(logN)
        for _ in range(k-1):
            nums[0] = small 
            Heapify(nums, 0, N-1)
        return nums[0]

3.3.11 最小的k个数

LeetCode 剑指 Offer 40.最小的k个数 | | 返回目录3.3

思路： 由于此题没有要求时间复杂度，可以直接调用原生sort函数，或者用任意一种排序方法，先排序。
如果要追求时间复杂度较低的话，和上一道题有异曲同工之妙，此题找到是最小的k个数，所以仍然可以复用方法。

• 写法一：直接调用sort

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[:k]

• 写法二：复用上一题目的思路

  class Solution:
      def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
          '''由于和上一题几乎一样，这里仅给出用自带的heapq的code，其他的不赘述'''
          import heapq
          heapq.heapify(arr)
          res = []
          for i in range(k):
              res.append(arr[0])
              heapq.heappop(arr)
          return res
          # 甚至可以直接调用求最小的n个函数
          # return heapq.nsmallest(k, arr)

3.3.12 多数元素

LeetCode 169.多数元素| | | 返回目录3.3

思路：该题就是先排序，至于排序方法可以任选，反正没有要求时间复杂度。拍完序后，该数一定会出现在 [n/2]位置，因为它的个数超过了[n/2]

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

3.3.13 合并两个有序数组

LeetCode 88.合并两个有序数组 | | 返回目录3.3

思路 1：这个题一看就知道可以用归并排序中的 【归并】步骤做。
只不过这里是直接在nums1上进行填充（题目中nums1的空间是有冗余的），所以对nums1从右往左进行填充。
这样的话就是从右往左遍历，较大数往nums1右侧填充即可。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
    
        p1, p2 = m-1, n-1
        i = m+n-1
        # p1, p2, i 都是从右往左遍历
        # 较大数往 i 位置填充
        while p1 >=0 and p2 >=0 :
            if nums1[p1] > nums2[p2]:
                nums1[i] =  nums1[p1] 
                p1 -= 1
                i-=1
            else:
                nums1[i] =  nums2[p2] 
                p2 -= 1
                i-=1
        # 如果 p1 >= 0，说明 nums2的数已经全部填入合适位置了
        # 那 nums1剩下的部分可以不用动，所以这部分可以注释掉
        # while p1 >= 0:
        #     nums1[i] =  nums1[p1]
        #     p1 -= 1
        #     i-=1

        while p2 >= 0:
            # 如果nums2还有剩余，就继续填充即可
            nums1[i] =  nums2[p2]
            p2 -= 1
            i-=1

思路 2：因为 nums1 也已经是有序部分，所以可以用插入排序的思路做，即将 nums2 中的元素逐个插入到 nums1 中合适的位置即可。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # .插入排序
        # 换句话说nums1 在 (0,m) 区间 已经有序了
        # 那可以用插入排序，将 nums2的数一个一个插入到合适的位置
        # 只需要考察 m 到 m+n-1 的位置了
        for i in range(m, m+n):
            nums1[i] = nums2[i-m]
            for j in range(i-1,-1,-1):
                if nums1[j] > nums1[j+1]:
                    nums1[j+1], nums1[j] = nums1[j], nums1[j+1]

3.3.14 逆序对

LCR 170. 交易逆序对的总数 | | 返回目录3.3

思路：如果用暴力手段去遍历的话，可能会超时。逆序对问题，可以用归并排序的过程来求解，具体的讲解放在注释中了。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:

        # 就是手写归并排序，只不过这里需要多传入一个统计量 cnt 参与计数
        '''核心思想就是在归并操作，对比左右两部分的数字的时候，
           考察右侧的每一个数，在左边有多少个数比它大，则左边的这些数就都能与右侧的该数，
           组成逆序对
        '''
        def func(a, L, R, cnt):
            if L >= R :
                return cnt 
            
            M = L + (R-L) // 2

            cnt = func(a,L,M,cnt)
            cnt = func(a,M+1,R,cnt)

            # merge 
            p1, p2 = L, M+1
            res = []
            while p1<=M and p2 <=R:
                if a[p1] <= a[p2]:
                    # 左边的比右边的小，不构成逆序对，不用考虑
                    res.append(a[p1])
                    p1+=1
                    
                else: # a[p1] > a[p2]
                    # 因为归并排序的特点，左右两部分都各自已经是有序的了
                    # 所以left部分的 [p1,M] 区间的数都比 a[p1] 大
                    # 那么自然也比a[p2]大，都可与a[p2]组成逆序对
                    cnt += M - p1 + 1
                    res.append(a[p2])
                    p2+=1     

            # 如果是左侧数组还剩余有元素
            # 说明右侧数组已经考察完了
            # 而我们上面的计算方案是，对于右侧数组中的数字，计算其在左侧有多少个比它大
            # 此时右侧数组已经考察完，就说明cnt不用再计算了
            while p1 <= M:
                res.append(a[p1])
                p1 += 1

            # 如果是右侧数组还剩余有元素
            # 说明左侧数组已经全部考察完了
            # 那么右侧数组剩余的数字一定是比左侧数组中的数字都大
            # 所以cnt也不用再计算了
            while p2 <= R:
                res.append(a[p2])
                p2 += 1

            for i in range(0,R-L+1):
                a[L+i] = res[i]

            return cnt
            
        return func(nums, 0, len(nums)-1, 0)

3.3.15 计算右侧小于当前元素的个数

LeetCode 315.计算右侧小于当前元素的个数 | | 返回目录3.3

思路：该题是上一题的升级版，难度稍微上升了一点。因为这一次等于是要计算对应位置上的逆序对，而位置在排序的时候是会移动的，就是要在这里考虑这一点。
所以排序的时候，可以带着索引一起排；这样对每个位置计算其各个merge阶段的逆序对的时候，还是按照索引来进行改动。
将索引和数字绑定在一起形成一个元素：nums2 = [[idx, num] for idx, num in enumerate(nums)]
另外，由于我们是对每个位置计算其右侧的逆序对，所以这个题中，在考虑计算逆序对的时机时，应该是以left数为准，计算右侧有多少个数比它小。（上一题在merge时，是对右侧的每个数计算其左侧有多少个数可以和其组成逆序对，因为只考虑逆序对的个数，而不考虑具体哪个位置上逆序对的个数，所以这么写code方便一些）

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # 先产生一个(索引，数字)为元素的新数组
        nums2 = [[idx, num] for idx,num in enumerate(nums)]
        # 初始化一个全0的结果list
        cnt_list = [0]*len(nums)

        def func(a, L, R):
            if L >= R:
                return 
            
            M = L + (R-L)//2
            func(a, L, M)
            func(a, M+1, R)

            p1, p2 = L, M+1
            tmp = []
            while p1 <= M and p2 <= R:
                # 元素是(idx, num)
                # 所以这里要对比的是 p1 和 p2 位置上的第二个值：num
                if a[p1][1]<=a[p2][1]:
                    # 此时轮到左侧 p1 位置上的元素进入tmp
                    # 说明右侧的 [M+1, p2-1] 区间先于 p1的数字进入 tmp
                    # 即右侧的 [M+1, p2-1]区间 比 p1位置的数小

                    # 获取 a[p1][0]，对该位置记录的逆序对进行修改
                    cnt_list[a[p1][0]] += p2 - (M+1)
                    tmp.append(a[p1])
                    p1 += 1
                else:
                    tmp.append(a[p2])
                    p2 += 1

            # 如果左侧数组还剩下数字没有进入tmp
            # 那说明剩下的这些数字都比右侧数组的数大            
            while p1 <= M:
                cnt_list[a[p1][0]] += p2 -(M+1)
                tmp.append(a[p1])
                p1 += 1    

            # 如果是右侧数组还剩下数字，说明左侧的已经考察完了
            # 由于我们的计算方案是对每个左侧数字计算右侧中比它大的数，
            # 所以此时不用变动cnt了
            while p2 <= R:
                tmp.append(a[p2])
                p2 += 1       

            for i in range(len(tmp)):
                a[L+i] = tmp[i]
            return 

        func(nums2, 0, len(nums)-1)                     
        return  cnt_list  

3.3.16 最接近原点的 K 个点

LeetCode 973.最接近原点的 K 个点 | | 返回目录3.3

思路：这个题最简单的思路就是排序时的条件设置为距离。不管是用自带的sort还是自己写的排序code，只要两个元素之间的大小关系的对比，设置为自定义即可。和3.3.2以及 3.3.3的核心思想一样。

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # 这里简便起见，直接使用自带的sort方法
        points.sort(key=lambda x: x[0]*x[0] + x[1]*x[1])

        return points[:k]

        # 如果要使用自己写的排序code，就需要定义一个比较大小的函数
        # 根据其返回值确定两个元素谁大，然后套用各种排序code即可
        # def Compare_two_ele(x,y):
        #     if x[0]*x[0] + x[1]*x[1]  > y[0]*x[0] + y[1]*y[1]:
        #         return 1
        #     elif x[0]*x[0] + x[1]*x[1] == y[0]*x[0] + y[1]*y[1]:
        #         return 2
        #     else:
        #         return 3