本文共 448 字,大约阅读时间需要 1 分钟。
题目传送门:
描述
有一个整形数组A,请设计一个复杂度为O(n)的算法,算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n,请返回最大的差值。保证数组元素多于1个。
[1,2,5,4,6],5
返回:2最优解思想来自桶排序,但并非桶排序算法,时间复杂度和空间复制度都为O(N);
AC代码
using namespace std;class Gap {public: int maxGap(vector a, int n) { if(n<=1) return 0; int Min = a[0],Max = a[0]; for (int i=1; iflags(n+1,false); vector minNum(n+1,INT_MAX),maxNum(n+1,INT_MIN); for (int i=0; i
转载地址:http://ihhji.baihongyu.com/