【Leetcode】164. Maximum Gap 【基数排序】
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
- Try to solve it in linear time/space.
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-gap
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
=======================================================================
【分析】
这道题目最简单的思路就是使用自带的排序函数先排序,然后比较计算相邻量元素差值并求出最大值。时间复杂度为O(nlogn)。但题目中提到最好用线性时间复杂度来解决,引入一种更快捷的排序方法,基数排序。
基数排序:
1. 从最低位(或最高位)开始,根据每个元素该为数字大小进行排序(若该为相等的元素则维持原有的前后顺序);
2.组成新的数组后再根据高一位的数字大小对元素按相同方法进行排序;
3.直到根据数组中最大的数字的最高位排序后,即可得到一个有序数组。
Eg. 原数组:
[ 10, 22, 19, 43, 72, 1, 8, 312]
根据个位数字排序后变为: [10, 1, 22, 72, 312, 43, 8, 19]
根据十位数字排序后变为: [1, 8, 10, 312, 19, 22, 43, 72]
根据百位数字排序后变为: [1, 8, 10, 19, 22, 43, 72, 312]
【参考代码】
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if(n < ) return ;
vector<int> aux(n, );
int exp = ; int maxN = *max_element(nums.begin(), nums.end());
while(maxN/exp > ) {
vector<int> count(, );
for(int n: nums) {
count[(n/exp)%]++;
}
for(int i = ; i < ; i++) {
count[i] += count[i-];
}
for(int i = n-; i >= ; --i) {
int n = nums[i];
aux[--count[(n/exp)%]] = n;
}
for(int i = ; i < n; ++i) {
nums[i] = aux[i];
}
exp *= ;
}
int res = ; for(int i = ; i < n; ++i) {
//cout << nums[i-1] << ", ";
res = max(res, nums[i]-nums[i-]);
}
return res;
}
};
【代码分析】
使用count[d]. 先用count[d]来统计当前的位数中数字为d的元素个数,后进行处理,使count[d]表示小于等于d的元素总数。
之后可从后向前遍历nums, 根据元素当前位数中的数字决定他应该在新数组(aux)中的位置:
最后一个当前位等于d的元素,应该处于count[d]-1的位置;放入该元素后,把count[d]减一,便为下一个当前位等于d的元素的位置+1。
时间复杂度:O(d*(n+10)) 约等于O(n)
最新文章
- System.getProperty()方法大全
- 推荐学习使用cocoapods和phoneGap安装的链接
- Arduino 极速入门系列 - 光控灯(3) - 光敏电阻、与电阻分压那些事
- php统计字数函数
- CentOS 常用命令大全
- 上次遗留下来的XMLUtil的问题
- T-SQL切割字符串方法小结 2
- vijos 1234 口袋的天空
- iOS安全攻防之使用 Frida 绕过越狱设备检测
- CentOS7.3虚拟机扩展数据磁盘
- 前端传送JSON数据,报Required request body is missing
- python 二分法模板——牢记
- 初学git
- ACM基础(一)
- 三种文本特征提取(TF-IDF/Word2Vec/CountVectorizer)及Spark MLlib调用实例(Scala/Java/python)
- CentOS7安装MySQL5.7常见问题
- tar打包排除某个文件夹
- poj 2096 Collecting Bugs &;&; ZOJ 3329 One Person Game &;&; hdu 4035 Maze——期望DP
- LINUX gcc安装rpm包顺序
- 为什么需要学UML建模