0912. Sort an Array¶
题目信息¶
- 题号:
0912
- 难度:
Medium
- 主题:
数组、整数排序、重复元素
- 原题:
- 重点:
返回包含相同元素及相同重复次数的非递减排列;不得调用内置排序函数,要求
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]
解释:单元素数组已经按非递减顺序排列,返回值仍包含原来的唯一元素。