LeetCode 315 Count of Smaller Numbers After Self

LeetCode

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 1:

Input: nums = [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.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

1 <= nums.length <= 10<sup>5</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

题目大意：

数组中，统计每一位比自己小的数。

解题思路：

一开始考虑用递减栈。但不可行, 因为这是统计题，而不是求比自己大的一个数LeetCode 503 Next Greater Element II。类似于merge sort，考虑统计逆序数

解题步骤：

N/A

注意事项：

1. 由于mergesort会改变数组顺序，所以统计数组count也要对应的数也会变，所以将原数组变成(数值, 下标)对，count就可以统计原数组
2. 计算逆序对时候，放在nums[i][0] <= nums[j][0]中，核心在count[nums[i][1]] += j - mid - 1

Python代码：

def countSmaller(self, nums: List[int]) -> List[int]:
	count = [0] * len(nums)
	num_with_idx = [(n, i) for i, n in enumerate(nums)]
	self.merge_sort(num_with_idx, 0, len(nums) - 1, count)
	return count

def merge_sort(self, nums, start, end, count):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.merge_sort(nums, start, mid, count)
	self.merge_sort(nums, mid + 1, end, count)
	self.merge(nums, start, mid, end, count)

def merge(self, nums, start, mid, end, count):
	i, j = start, mid + 1
	res = []
	while i <= mid and j <= end:
		if nums[i][0] <= nums[j][0]:
			res.append(nums[i])
			count[nums[i][1]] += j - mid - 1
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		count[nums[i][1]] += j - mid - 1
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)