题目
结果
代码
快排
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int maximumGap(int[] nums) {
if (nums.length <= 1) {
return 0;
}
Arrays.sort(nums);
int gap = Integer.MIN_VALUE;
for (int i = 0; i < nums.length - 1; i++) {
gap = Math.max(gap, nums[i + 1] - nums[i]);
}
return gap;
}
}
|
基数排序
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
| class Solution {
public int maximumGap(int[] nums) {
if (nums.length <= 1) {
return 0;
}
radixSort(nums);
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length - 1; i++) {
max = Math.max(max, nums[i + 1] - nums[i]);
}
return max;
}
private void radixSort(int[] nums) {
long exp = 1;
int[] buf = new int[nums.length];
int max = Arrays.stream(nums).max().getAsInt();
while (max >= exp) {
int[] cnt = new int[10];
for (int num : nums) {
int digit = (int) ((num / exp) % 10);
cnt[digit]++;
}
for (int i = 1; i < 10; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = nums.length - 1; i >= 0; i--) {
int digit = (int) (nums[i] / exp) % 10;
buf[cnt[digit] - 1] = nums[i];
cnt[digit]--;
}
System.arraycopy(buf, 0, nums, 0, nums.length);
exp *= 10;
}
}
}
|
复杂度
快排：
时间复杂度：O（N log N）
空间复杂度：O（log N），快排过程中递归需要的栈空间
基数排序：
时间复杂度：O（N）
空间复杂度：O（N）