GuilinDev

Lc1509

05 August 2008

1509 Minimum Difference Between Largest and Smallest Value in Three Moves

给一个数组 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;
    }
}