啥?你以为排序算法的时间复杂度最快也只能O(N*log(N))了?

O(N)时间复杂度的排序算法听说过没有?计数排序!!它是世界上最快最简单的算法!!!

计数排序算法操作起来只有三步,看完秒懂!

  1. 根据待排序集合中最大元素和最小元素的差值范围确定申请的桶个数;
  2. 遍历待排序集合,将每一个元素统计到对应的桶中;(此步完成后每个桶里面的数字代表了此桶对应元素出现的次数。)
  3. 从小到大遍历一遍所有桶,如果桶中有元素,那么就往排序结果里添加上对应个数的该桶对应的元素。

举个例子就明白了,假设已知所有待排序数字范围都在0~10,现在给了待排序的数组[5, 3, 5, 2, 8]。那么:

  1. 申请0~10共11个桶用于放元素。
  2. 遍历待排序的数组[5, 3, 5, 2, 8],把对应的桶里面放入小旗子,即 2、3、8 桶各放了一个旗子, 5 桶里放了两个旗子。
  3. 从 0 到 11 遍历一遍所有的桶,如果桶里没有小旗子就跳过,有小旗子就往结果里放入小旗子个数的该元素。得到[2, 3, 5, 5, 8]

是不是超级简单!

时间复杂度:数据取值范围是常数 M,待排序元素个数是 N,总的时间复杂度是 O(M + N) = O(N)!我们只把每个待排序的数字访问了一遍,所以是O(N)!
啥?你问我那 M 呢?M 是题目告诉你的数据取值范围呀,是个常数,和你要解决的问题规模无关!

空间复杂度:由于我们申请了大小为 M 的桶来放元素,所以空间复杂度是 O(M)。
啥?你问我那 N 呢?申请了 N 个空间用来存储要返回的结果,这个空间不算入空间复杂度!

既然计数排序的时间复杂度是 O(N) 那我们为啥不都使用计数排序呢?答案是只有当数字取值规模确定并且比较小的时候才能用呀,如果不知道取值规模或者取值规模太大,就不可以申请出那么多桶了呦~

本题告诉了取值范围是-50000 <= A[i] <= 50000,所以直接申请 100000 个桶就好了!

我们每个桶的下标是从 0 开始的,但是A[i]最小能取到 -50000,所以把 A[i] 映射到桶的下标的时候需要 + 50000;最后根据桶里面的元素放入到结果数组的时候要把桶的下标 - 50000还原成 A[i]。

我使用的C++代码作为演示。

class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int N = nums.size();
vector<int> counter(100010, 0);
for (int n : nums) {
counter[n + 50000] ++;
}
vector<int> res;
for (int i = 0; i < 100010; ++i) {
if (counter[i] != 0) {
res.insert(res.end(), counter[i], i - 50000);
}
}
return res;
}
};

欢迎关注负雪明烛的刷题博客,刷题800多,每道都记录了写法!

力扣每日一题活动建群啦,一起监督和讨论,我自建监督网址:http://group.ojeveryday.com/#/check,加入方式可以在监督网址中看到。

最新文章

  1. 分享我基于NPOI+ExcelReport实现的导入与导出EXCEL类库:ExcelUtility (续篇)
  2. 哈希表(Hash Table)
  3. tarjan算法求割点cojs 8
  4. [NetTopologySuite](1)线面相交
  5. linux命令总结2
  6. 【转】Enable ARC in a Cocos2D Project: The Step-by-Step-How-To-Guide Woof-Woof!
  7. 【转】silverlight 跨域访问
  8. 转:对于linux下system()函数的深度理解(整理)
  9. Python-方法重载的问题
  10. 主机和VMware中的Linux如实现共享文件夹
  11. c# 颜色RGB到HSB互相转换
  12. java中,用json格式转换遇到问题
  13. appium-doctor问题
  14. 吴恩达机器学习笔记5-梯度下降I(Gradient descent intuition)
  15. Git与GitHub学习笔记(七)Windows 配置Github ssh key
  16. 【转载】C++中替代sprintf的std::ostringstream输出流详解
  17. SuSE Linux Enterprise Server - 软件包下载地址
  18. Java_6 方法
  19. c#泛型与其他语言的对比(深入理解c#)
  20. java之ibatis数据缓存

热门文章

  1. window修改dns本地文件
  2. DNS域名解析全过程
  3. Linux之vi和vim编辑器
  4. js判断undefined nan等
  5. C++你不知道的事
  6. python2 第二天
  7. Spring Boot 创建定时任务(配合数据库动态执行)
  8. vue中vuex的五个属性和基本用法
  9. 命令行方式运行hadoop程序
  10. @NotBlank 注解不生效