题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tqId=23260&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
因题目要求时间复杂度为O(nlogn)，所以选用时间复杂度稳定为O(nlogn)的归并排序解决此问题。逆序对的个数其实就是在数组中值小的元素在排序过程中与位置靠前的值比它大的元素做交换位置的次数。理解了这个概念之后我们就可以在排序过程中记录这个次数，我定义了一个类属性counter来记录这个次数，在归并排序中主要步骤是合并两个有序数组，那么我们从递归过程中来看，右侧数组中值小的元素，需要排在左侧数组中值比它大的元素之前，那么左侧数组中值比它大的元素有几个，则组成的逆序对就有几个，此时counter就需要加上这个个数，我们想一下，这个值应该是代码中的length_a-a的值。解释一下，a之前的元素肯定是小于b对应的元素的，a之后的才是大于的，那么大于b对应的值的元素个数就应该是a数组的长度减去a。剩下没啥可说的了，就是归并排序的逻辑。
#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def __init__(self):
self.counter = 0
def InversePairs(self , nums ):
# write code here
def merge_sorted_list(sorted_a, sorted_b):
length_a, length_b = len(sorted_a), len(sorted_b)
a = b = 0
new_sorted_seq = []
while a < length_a and b < length_b:
if sorted_a[a] < sorted_b[b]:
new_sorted_seq.append(sorted_a[a])
a += 1
else:
new_sorted_seq.append(sorted_b[b])
b += 1
self.counter += length_a-a
if a < length_a:
new_sorted_seq.extend(sorted_a[a:])
else:
new_sorted_seq.extend(sorted_b[b:])
return new_sorted_seq
def mergesort(nums):
if len(nums) <= 1:
return nums
else:
mid = int(len(nums)/2)
left_half = mergesort(nums[:mid])
right_half = mergesort(nums[mid:])
return merge_sorted_list(left_half, right_half)
mergesort(nums)
return self.counter % 1000000007
第一次写题解，可能写的还不够清晰好懂，欢迎各位大神指教
#归并排序#
查看1道真题和解析
