第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0912. 排序数组

题目地址(912. 排序数组)

题目描述

1
给你一个整数数组 nums,请你将该数组升序排列。
2
3
4
5
示例 1:
6
7
输入:nums = [5,2,3,1]
8
输出:[1,2,3,5]
9
示例 2:
10
11
输入:nums = [5,1,1,2,0,0]
12
输出:[0,0,1,1,2,5]
13
14
15
提示:
16
17
1 <= nums.length <= 50000
18
-50000 <= nums[i] <= 50000
Copied!

前置知识

  • 数组
  • 排序

公司

  • 阿里
  • 百度
  • 字节

思路

这是一个很少见的直接考察排序的题目。 其他题目一般都是暗含排序,这道题则简单粗暴,直接让你排序。 并且这道题目的难度是Medium, 笔者感觉有点不可思议。
我们先来看题目的限制条件,这其实在选择算法的过程中是重要的。 看到这道题的时候,大脑就闪现出了各种排序算法, 这也算是一个复习排序算法的机会吧。
题目的限制条件是有两个,第一是元素个数不超过 10k,这个不算大。 另外一个是数组中的每一项范围都是-50k50k(包含左右区间)。 看到这里,基本我就排除了时间复杂度为 O(n^2)的算法。
我没有试时间复杂度 O(n^2) 的解法,大家可以试一下,看是不是会 TLE。
剩下的就是基于比较的nlogn算法,以及基于特定条件的 O(n)算法。
由于平时很少用到计数排序等 O(n)的排序算法,一方面是空间复杂度不是常量,另一方面是其要求数据范围不是很大才行,不然会浪费很多空间。 但是这道题我感觉可以试一下。 在这里,我用了两种方法,一种是计数排序,一种是快速排序来解决。 大家也可以尝试用别的解法来解决。

解法一 - 计数排序

时间复杂度 O(n)空间复杂度 O(m) m 为数组中值的取值范围,在这道题就是50000 * 2 + 1
我们只需要准备一个数组取值范围的数字,然后遍历一遍,将每一个元素放到这个数组对应位置就好了, 放的规则是索引为数字的值,value为出现的次数
这样一次遍历,我们统计出了所有的数字出现的位置和次数。 我们再来一次遍历,将其输出到即可。
sort-an-array-1

解法二 - 快速排序

快速排序和归并排序都是分支思想来进行排序的算法, 并且二者都非常流行。 快速排序的核心点在于选择轴元素。
每次我们将数组分成两部分,一部分是比 pivot(轴元素)大的,另一部分是不比 pivot 大的。 我们不断重复这个过程, 直到问题的规模缩小的寻常(即只有一个元素的情况)。
快排的核心点在于如何选择轴元素,一般而言,选择轴元素有三种策略:
  • 数组最左边的元素
  • 数组最右边的元素
  • 数组中间的元素(我采用的是这种,大家可以尝试下别的)
  • 数组随机一项元素
sort-an-array-2
图片中的轴元素是最后面的元素,而提供的解法是中间元素,这点需要注意,但是这并不影响理解。

关键点解析

  • 排序算法
  • 注意题目的限制条件从而选择合适的算法

代码

计数排序:
代码支持: JavaScript
1
/**
2
* @param {number[]} nums
3
* @return {number[]}
4
*/
5
var sortArray = function (nums) {
6
const counts = Array(50000 * 2 + 1).fill(0);
7
const res = [];
8
for (const num of nums) counts[50000 + num] += 1;
9
for (let i in counts) {
10
while (counts[i]--) {
11
res.push(i - 50000);
12
}
13
}
14
return res;
15
};
Copied!
快速排序:
代码支持: JavaScript
1
function swap(nums, a, b) {
2
const temp = nums[a];
3
nums[a] = nums[b];
4
nums[b] = temp;
5
}
6
7
function helper(nums, start, end) {
8
if (start >= end) return;
9
const pivotIndex = start + ((end - start) >>> 1);
10
const pivot = nums[pivotIndex];
11
let i = start;
12
let j = end;
13
while (i <= j) {
14
while (nums[i] < pivot) i++;
15
while (nums[j] > pivot) j--;
16
if (i <= j) {
17
swap(nums, i, j);
18
i++;
19
j--;
20
}
21
}
22
helper(nums, start, j);
23
helper(nums, i, end);
24
}
25
26
/**
27
* @param {number[]} nums
28
* @return {number[]}
29
*/
30
var sortArray = function (nums) {
31
helper(nums, 0, nums.length - 1);
32
return nums;
33
};
Copied!

扩展

  • 你是否可以用其他方式排序算法解决?
  • 你可以使用同样的算法对链表进行排序么?(大家可以用力扣 148.排序链表 进行验证哦)

参考