LeetCode-315. Count of Smaller Numbers After Self

目录

题目描述

解题思路

【C++】

【Java】

复杂度分析

---

LeetCode-315. Count of Smaller Numbers After Selfhttps://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

题目描述

Given an integer array nums, return an integer array counts 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 <= 105
• -104 <= nums[i] <= 104

解题思路

【C++】

class Solution {
private:vector<int> index{};vector<int> tmpIndex{};vector<int> ans{};void merge(vector<int>& nums, int start, int mid, int end) {int p1 = start, p2 = mid + 1, cur = start, len = end - start + 1;while (p1 <= mid && p2 <= end) {if (nums[index[p1]] > nums[index[p2]]) {ans[index[p1]] += end - p2 + 1;tmpIndex[cur++] = index[p1++];} else {tmpIndex[cur++] = index[p2++];}}while (p1 <= mid) {tmpIndex[cur++] = index[p1++];}while (p2 <= end) {tmpIndex[cur++] = index[p2++];}for (int i = start; i <= end; i++) {index[i] = tmpIndex[i];}}void mergeSort(vector<int>& nums, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}}public:vector<int> countSmaller(vector<int>& nums) {index.resize(nums.size());tmpIndex.resize(nums.size());ans.resize(nums.size(), 0);for (int i = 0; i < nums.size(); i++) {index[i] = i;}mergeSort(nums, 0, nums.size() - 1);return ans;}
};

【Java】

class Solution {private int[] index;private int[] tmpIndex;private List<Integer> ans;private void merge(int[] nums, int start, int mid, int end) {int p1 = start, p2 = mid + 1, cur = start, len = end - start + 1;while (p1 <= mid && p2 <= end) {if (nums[index[p1]] > nums[index[p2]]) {ans.set(index[p1], ans.get(index[p1]) + end - p2 + 1);tmpIndex[cur++] = index[p1++];} else {tmpIndex[cur++] = index[p2++];}}while (p1 <= mid) {tmpIndex[cur++] = index[p1++];}while (p2 <= end) {tmpIndex[cur++] = index[p2++];}for (int i = start; i <= end; i++) {index[i] = tmpIndex[i];}}private void mergeSort(int[] nums, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}}public List<Integer> countSmaller(int[] nums) {index = new int[nums.length];tmpIndex = new int[nums.length];ans = new ArrayList<Integer>(nums.length);for (int i = 0; i < nums.length; i++) {index[i] = i;ans.add(0);}mergeSort(nums, 0, nums.length - 1);return ans;}
}

复杂度分析

• 时间复杂度：O(nlogn)，即归并排序的时间复杂度。
• 空间复杂度：O(n)，这里归并排序的下标映射数组、临时下标映射数组以及答案数组的空间代价均为 O(n)。
• 注意：不建议在merge函数内创建临时下标映射数组，那样做会反复申请和销毁资源，消耗较大。