912.排序数组（计数排序）
目录
- 题目
- 解法
题目
给你一个整数数组 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;
}
};