912. 排序数组
- 912. 排序数组
题目
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
题解
- 接收一个数组 nums，通过计数排序的方法对数组进行排序，并返回排序后的新数组 newArr
- 时间复杂度: O(n+k)
找出最大值和最小值的循环遍历了数组 nums 一次，时间复杂度为O(n) ，其中 n是数组 nums 的长度。
统计元素出现次数的循环也遍历了数组 nums 一次，时间复杂度为O(n) 。
根据计数数组重建排序后的数组的循环遍历了计数数组 arr 一次，时间复杂度为O(k) ，其中k是计数数组的长度（k=max - min +1）。
总的时间复杂度为O(n+k)。
/*** @param {number[]} nums* @return {number[]}*/
var sortArray = function (nums) {// 找最大最小值let max = 0;let min = 0;for (let i = 0; i < nums.length; i++) {max = max > nums[i] ? max : nums[i];min = min < nums[i] ? min : nums[i];}const newArr = [];// 初始化数组长度为参数长度const arr = new Array(max - min + 1).fill(0);// 统计每一个值出现的次数for (let i = 0; i < nums.length; i++) {let arrIndex = nums[i] - min;if (arr[arrIndex] !== undefined) {arr[arrIndex] += 1;} else {arr[arrIndex] = 1;}}// 把有值的数据放到新数组里for (let i = 0; i < arr.length; i++) {const list = new Array(arr[i]).fill(min + i);newArr.push(...list);}return newArr;
};
