05 August 2008
给一个数组 nums ,每次操作以选择 nums 中的任意一个元素并将它改成任意值。
返回三次操作后, nums 中最大值与最小值的差的最小值。
排序,即可直接得到其中最大的四个数与最小的四个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
if (n <= 4) {
return 0;
}
Arrays.sort(nums);
int ret = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
ret = Math.min(ret, nums[n - 4 + i] - nums[i]);
}
return ret;
}
}
贪心,直接维护最大的四个数与最小的四个数即可,我们用两个数组分别记录最大值与最小值,不断更新这两个最值数组。
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
class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
if (n <= 4) {
return 0;
}
int[] maxn = new int[4];
int[] minn = new int[4];
Arrays.fill(maxn, -1000000000);
Arrays.fill(minn, 1000000000);
for (int i = 0; i < n; i++) {
int add = 0;
while (add < 4 && maxn[add] > nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
maxn[j] = maxn[j - 1];
}
maxn[add] = nums[i];
}
add = 0;
while (add < 4 && minn[add] < nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
minn[j] = minn[j - 1];
}
minn[add] = nums[i];
}
}
int ret = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
ret = Math.min(ret, maxn[i] - minn[3 - i]);
}
return ret;
}
}