0912. Sort an Array

题目信息

题号:

0912

难度:

Medium

主题:

数组、整数排序、重复元素

原题:

LeetCode 0912

重点:

返回包含相同元素及相同重复次数的非递减排列;不得调用内置排序函数,要求 O(n log n) 时间并尽量减少额外空间

题目重述

给定整数数组 nums,请把其中全部元素按非递减顺序排列并返回排序后的数组。

结果必须保留输入中的每个元素及其出现次数。数组可能包含负数和重复值;题目不要求排序过程稳定,也不要求原地修改输入。实现时不能使用语言提供的内置排序函数,并应达到 O(n log n) 时间复杂度,同时使用尽可能少的额外空间。

1 <= nums.length <= 5 * 10^4,-5 * 10^4 <= nums[i] <= 5 * 10^4。

自建示例

包含负数和重复值:

输入:nums = [4,-1,4,2]
输出:[-1,2,4,4]
解释:两个 4 都必须保留,所有元素按从小到大的非递减顺序排列。

数组只有一个元素:

输入:nums = [-7]
输出:[-7]
解释:单元素数组已经按非递减顺序排列,返回值仍包含原来的唯一元素。