解法1：
使用任意一种时间复杂度为O（nlogn）的排序算法（如快速排序）给原数组排序，然后遍历排好序的数组，并对每两个相邻元素求差。
复杂度：时间O（nlogn），在不改变原数组的情况下，空间复杂度是O(n)
解法2：基数排序的思想
- 利用计数排序的思想，先求出原数组的最大值max与最小值min的区间长度k（k=max-min+1），以及偏移量d=min。
- 创建一个长度为k的新数组Array。
- 遍历原数组，每遍历一个元素，就把新数组Array对应下标的值+1。例如原数组元素的值为n，则将Array[n-min]的值加1。遍历结束
后，Array的一部分元素值变成了1或更高的数值，一部分元素值仍然是0。
- 遍历新数组Array，统计出Array中最大连续出现0值的次数+1，即为相邻元素最大差值。
解法3：桶排序的思想
解法3：
- 利用桶排序的思想，根据原数组的长度n，创建出n个桶，每一个桶代表一个区间范围。其中第1个桶从原数组的最小值min开始，区间跨
度是（max-min）/（n-1）。
- 遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大和最小值。
- 遍历所有的桶，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。
时间复杂度是O（n），空间复杂度是O（n*k）
代码C++版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include<iostream>
#include <algorithm>
#include"memory.h"
using namespace std;
struct bucket{
int min;
int max;
bucket():min(NULL),max(NULL){}
};
int getmaxdtce(int *a,int n)
{
int *max = max_element(a,a+n);
int *min = min_element(a,a+n);
int d = *max - *min;
if(d==0)
{
return 0;
}
int bucketnum = n;
bucket *buckets = new bucket[n];
for (int i = 0; i < n;i++)
{
int index = (a[i] - *min) / (d / (bucketnum - 1));
if(buckets[index].min==NULL||buckets[index].min>a[i])
{
buckets[index].min = a[i];
}
if(buckets[index].max==NULL||buckets[index].max>a[i])
{
buckets[index].max = a[i];
}
}
int leftmax = buckets[0].max;
int maxdistance = 0;
for (int i = 1; i < n;i++)
{
if(buckets[i].min==NULL){
continue;
}
if(buckets[i].min-leftmax>maxdistance)
{
maxdistance = buckets[i].min - leftmax;
}
leftmax = buckets[i].max;
}
return maxdistance;
}
int main(int argc,char *argv[] )
{
int *test = new int[5];
memset(test, 0, sizeof(int) * 5);
test[0] = 1;test[1] = 6;
test[2] = 3;
test[3] = 8;
test[4] = 0;
cout <<getmaxdtce(test,5);
}
|
