Bucket Sort - leetcode [桶排序]
桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是比较排序,他不受到O(n log n)下限的影响。
桶排序以下列程序进行:
- 设置一个定量的数组当作空桶子。
- 寻访序列,并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
鸽巢排序(Pigeonhole sort),也被称作基数分类,是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用。
164. Maximum Gap
We divide the range of array into array.size() interval, where k = (maximum-minimum) / n.
[minimum, minimum + k), [minimum + k, minimum + 2k), ... , [minimum + (n-1)k, maximum]
And we uses two extra array "max_in_interval" and "min_in_interval" to record the maximum and minimum of each interval.
First, let's considering an uniformly distributed array of n numbers. By which I mean,
[minimum, minimum + k), [minimum + k, minimum + 2k), ... , [minimum + (n-1)k, maximum]
n intervals each contains a single number. we could easily find the maximum gap by calculate min_in_interval[i+1] - max_in_interval[i]
Now comes the most important observation. If any single interval contains more than 1 number, then there must be an empty interval, and maximum gap is larger than a single interval. By which I mean if multiple numbers appear in the same interval, we can safely ignore the numbers which lies in the middle of interval(not max_in_interval nor min_in_interval).
最新文章
- Mac上自带的Apache介绍
- java如何跳出多重嵌套循环
- 【Java EE 学习 50】【Spring学习第二天】【使用注解的DI实现】【spring中的继承】【动态代理伪hibernate实现】
- 【drp 11】使用Junit简单测试接口方法
- HIV T2
- [原]android不支持命名的semaphore
- ###Maintainable C++
- 【好文转载c++】 sizeof 使用的经典总结
- asp.net中ScriptManager自带Ajax与jQuery事件冲突
- 学习FFmpeg API – 解码视频
- easing--缓动函数--贝塞尔函数--圆盘转动抽奖应用
- OLE:对象的类没有在注册数据库中注册
- __x__(35)0908第五天__ 层级 z-index
- odoo定时发送邮件
- 推荐一个SAM文件或者bam文件中flag含义解释工具
- Java进程&线程(整理)
- 存储区域网络(Storage Area Network,简称SAN)
- Python记录8:函数的嵌套
- AndroidManifest中注册application
- P4论文粗读笔记(一)
热门文章
- 我看TDD测试驱动开发
- [置顶] Hibernate从入门到精通(十)多对多单向关联映射
- linux终端下文件不同颜色的含义
- Redis一些命令总结
- QuickWebApi2:使用Lambda方式,完成对WebApi的开发和调用-文档的生成
- 关于ADB server didn't ACK * failed to start daemon *的问题
- Oracle修改字段类型和长度
- ASP.NET MVC页面UI之联动下拉选择控件(省、市、县联动选择)
- Windbg是windows平台上强大的调试器
- enode框架step by step之框架的物理部署思路