算法现学现卖——归并排序求逆序对的升级版

作者:杨润炜
日期:2020/7/11 23:46

归并排序求逆序对的升级版

今天leetcode的每日一题 计算右侧小于当前元素的个数
先来试试暴力解法:

  1. class Solution:
  2. def countSmaller(self, nums: List[int]) -> List[int]:
  3. n = len(nums)
  4. counts = [0] * n
  5. for i in range(n):
  6. cur = nums[i]
  7. for j in range(i+1, n):
  8. if cur > nums[j]:
  9. counts[i] += 1
  10. return counts

结果是超时,时间复杂度是O(n^2)。这肯定是需要高级解法了。先把高级解法抛出来:归并排序求逆序对,且利用“索引数组”。

  • 不知道啥是逆序对?
    那先来了解下逆序对:某个数比后面的数大,这两个数就构成逆序对。

  • 忘记啥是归并排序?
    那先复习一道排序题吧

    归并排序

    排序数组
    关键还是递归的思想,将数组拆分为两份,每一份相当于独立的子问题,继续按前面的方法拆分,直到不可拆,再向上合并,合并的时候每一份数据即是有序的,首先不可拆时(一个元素)是有序的,两个数组合并为一个有序的大数组,再作为下一次的小数组与其它有序小数组合并,最终归到根节点,数组合并完成,元素即是有序的。
    如图,黑色为递的过程,将数据拆分,红色是归和并的过程,将有序的小数组合并为有序的大数组,最终将所有数据排序完成。
    归并排序
    代码实现如下:

    1. class Solution:
    2. def sortArray(self, nums: List[int]) -> List[int]:
    3. self.mergeSort(nums, 0, len(nums) - 1)
    4. return nums
    5. def mergeSort(self, nums, left, right):
    6. if left >= right:
    7. return
    8. mid = (left + right) // 2
    9. self.mergeSort(nums, left, mid)
    10. self.mergeSort(nums, mid + 1, right)
    11. self.merge(nums, left, right, mid)
    12. def merge(self, nums, left, right, mid):
    13. tmp = [0 for _ in range(right - left + 1)]
    14. i = left
    15. j = mid + 1
    16. k = 0
    17. while i <= mid and j <= right:
    18. if nums[i] <= nums[j]:
    19. tmp[k] = nums[i]
    20. i += 1
    21. else:
    22. tmp[k] = nums[j]
    23. j += 1
    24. k += 1
    25. while i <= mid:
    26. tmp[k] = nums[i]
    27. i += 1
    28. k += 1
    29. while j <= right:
    30. tmp[k] = nums[j]
    31. j += 1
    32. k += 1
    33. for p in range(len(tmp)):
    34. nums[left + p] = tmp[p]

归并排序求逆序对

相应的题目:剑指 Offer 51. 数组中的逆序对
对于统计逆序对数量,在归并的merge其实已经实现了,它会对比两个子数组元素的大小,这时可以统计左边数组元素比右边数组大的情况的数量。
有两种统计方法:

  1. 在左边元素小于或等于右边的时候统计,这时表明左边元素大于右边的右侧元素,且需要在右边元素多的情况下,再统计多一次;
  2. 在左边元素大于右边的时候统计,这时表明左边左侧元素比右边这个元素大,增加逆序对数量;
    这里采用第2种方法,实现比较简洁。
  1. class Solution:
  2. def reversePairs(self, nums: List[int]) -> int:
  3. return self.countBymergeSort(nums, 0, len(nums) - 1)
  4. def countBymergeSort(self, nums, left, right):
  5. if left >= right:
  6. return 0
  7. mid = (left + right) // 2
  8. return self.countBymergeSort(nums, left, mid) + self.countBymergeSort(nums, mid + 1, right) + self.merge(nums, left, right, mid)
  9. def merge(self, nums, start, end, mid):
  10. i = start
  11. j = mid + 1
  12. count = 0
  13. k = 0
  14. tmp = [0 for _ in range(end - start + 1)]
  15. while i <= mid and j <= end:
  16. if nums[i] <= nums[j]:
  17. tmp[k] = nums[i]
  18. k += 1
  19. i += 1
  20. else:
  21. count += (mid - i + 1)
  22. tmp[k] = nums[j]
  23. k += 1
  24. j += 1
  25. while i <= mid:
  26. tmp[k] = nums[i]
  27. k += 1
  28. i += 1
  29. while j <= end:
  30. tmp[k] = nums[j]
  31. k += 1
  32. j += 1
  33. for p in range(len(tmp)):
  34. nums[start + p] = tmp[p]
  35. return count

求解开篇题目

逆序的统计方法有了,现在离开篇题目只差一点了,因为前面的方法只是统计整个数组中逆序的数量,但开篇题目要求的是每个元素与其后面元素对比,逆序的数量。归并的时候其实是将每个元素与其后面元素的逆序数量累加起来,所以基本是符合要求的,只是排序之后元素可能与之前的位置不同,没办法对应到counts位置上。这时可以利用“索引数组”,实际排序的是该数组,对比是用的是索引对应的原数组的值。
举个“索引数组”在归并排序中的例子,如图所示:
索引数组

代码实现如下:

  1. '''
  2. 归并排序 + 索引数组
  3. '''
  4. class Solution:
  5. def countSmaller(self, nums: List[int]) -> List[int]:
  6. size = len(nums)
  7. indexes = [i for i in range(size)]
  8. res = [0] * size
  9. self.countByMergeSort(nums, 0, size - 1, indexes, res)
  10. return res
  11. def countByMergeSort(self, nums, left, right, indexes, res):
  12. if left >= right:
  13. return
  14. mid = (left + right) // 2
  15. self.countByMergeSort(nums, left, mid, indexes, res)
  16. self.countByMergeSort(nums, mid + 1, right, indexes, res)
  17. self.merge(nums, left, right, mid, indexes, res)
  18. def merge(self, nums, left, right, mid, indexes, res):
  19. tmp = [0] * (right - left + 1)
  20. i = left
  21. j = mid + 1
  22. k = 0
  23. while i <= mid and j <= right:
  24. if nums[indexes[i]] <= nums[indexes[j]]:
  25. tmp[k] = indexes[i]
  26. k += 1
  27. i += 1
  28. res[indexes[i]] += j - mid - 1
  29. else:
  30. tmp[k] = indexes[j]
  31. k += 1
  32. j += 1
  33. while i <= mid:
  34. tmp[k] = indexes[i]
  35. k += 1
  36. i += 1
  37. res[indexes[i]] += right - mid
  38. while j <= right:
  39. tmp[k] = indexes[j]
  40. k += 1
  41. j += 1
  42. for p in range(len(tmp)):
  43. indexes[left + p] = tmp[p]

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/113.html
邮箱:glowrypauky@gmail.com
QQ: 892413924