题目

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

解法

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// CountSort 计数排序int n = nums.size();int minNum = INT_MAX, maxNum = INT_MIN;// 找到数组中的最小和最大元素for (int i = 0; i < n; ++i) {if (nums[i] < minNum) minNum = nums[i];if (nums[i] > maxNum) maxNum = nums[i];}// 构造计数数组vector<int> counts(maxNum - minNum + 1, 0);for (int i = 0; i < n; ++i) {++counts[nums[i] - minNum];}// 计数排序int index = 0;for (int i = 0; i < counts.size(); ++i) {while (counts[i] != 0) {nums[index++] = i + minNum;counts[i]--;}}return nums;}
};