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)
【Leetcode】164. Maximum Gap 【基数排序】的更多相关文章
-
LeetCode 164. Maximum Gap[翻译]
164. Maximum Gap 164. 最大间隔 Given an unsorted array, find the maximum difference between the successi ...
-
leetcode[164] Maximum Gap
梅西刚梅开二度,我也记一题. 在一个没排序的数组里,找出排序后的相邻数字的最大差值. 要求用线性时间和空间. 如果用nlgn的话,直接排序然后判断就可以了.so easy class Solution ...
-
[LeetCode] 164. Maximum Gap 求最大间距
Given an unsorted array, find the maximum difference between the successive elements in its sorted f ...
-
✡ leetcode 164. Maximum Gap 寻找最大相邻数字差 --------- java
Given an unsorted array, find the maximum difference between the successive elements in its sorted f ...
-
Java for LeetCode 164 Maximum Gap
Given an unsorted array, find the maximum difference between the successive elements in its sorted f ...
-
【刷题-LeetCode】164 Maximum Gap
Maximum Gap Given an unsorted array, find the maximum difference between the successive elements in ...
-
【LeetCode】164. Maximum Gap (2 solutions)
Maximum Gap Given an unsorted array, find the maximum difference between the successive elements in ...
-
【leetcode】Maximum Gap
Maximum Gap Given an unsorted array, find the maximum difference between the successive elements in ...
-
【leetcode】Maximum Gap(hard)★
Given an unsorted array, find the maximum difference between the successive elements in its sorted f ...
随机推荐
-
虚拟机下CentOS 配置IP地址的三种方法
1.自动获取IP地址(我不是用的这种方法,不做过多介绍) 虚拟机使用桥接模式,相当于连接到物理机的网络里,物理机网络有DHCP服务器自动分配IP地址. #dhclient 自动获取ip地址命令 #if ...
-
NYOJ之奇偶数分离
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAscAAAJ8CAIAAACdmZvPAAAgAElEQVR4nO3dPVLjStsG4G8T5CyEFC
-
【Android开发学习笔记】【第十课】运动事件 之——触摸屏
概念 触摸屏 (TouchScreen) 和 滚动球(TrackBall)是Android 中除了键盘之外的主要输入设备. 而这两个事件都可以用运动事件(MotionEvent)用于接收他们的信息 直 ...
-
[示例]NSEnumerator-使用枚举类型实现数组的逆序输出
代码: #import <Foundation/Foundation.h> int main(int argc, const char * argv[]) { @autoreleasepo ...
-
奇怪的Lisp和难懂的计算机程序的构造和解释
最近用新买的 Kindle 看<黑客与画家>的Lisp部分,发现作者 Paul Graham 很推崇 Lisp 语言,并且认为其它语言都没有Lisp简洁“成熟”,并且举例证明其它语言都在往 ...
-
谈谈.NET程序集(一)
谈谈.NET程序集(一) The Assembly in .NET by 唐小崇 http://www.cnblogs.com/tangchong 在.NET出现之前, Windows的程序有一些非常 ...
-
Linux学习之系统的构建
实验环境:ubuntu 12.04 LTS 内核版本:linux-3.9.4 因为一直以来都对Linux的工作机理比较感兴趣,所以正好这两天有机会好好的研究一下,那闲话不多说,直接进入正题. 俗话说的 ...
-
nodejs调试总结
之前nodejs开发中最痛苦的就是调试,因为我之前开发node时使用的编辑器还没有将nodejs的调试也集成进去,所以简单对nodejs开发的调试做了点探索,nodejs本身就有调试功能,同时node ...
-
Jmeter 测试工具
Jmeter的基本概念 百度百科: Apache JMeter是Apache组织开发的基于Java的压力测试工具.用于对软件做压力测试,它最初被设计用于Web应用测试,但后来扩展到其他测试领域. 它可 ...
-
6、nginx的反向代理及缓存功能
nginx模块的应用 ngx_http_proxy_module nginx 反向代理模块: http://nginx.org/en/docs/http/ngx_http_proxy_module. ...