阅读视图

学生分数的最小差值

2022年2月9日 10:18

方法一：排序

思路与算法

要想最小化选择的 $k$ 名学生中最高分和最低分的差值，我们一定是在排好序后的数组中连续地进行选择。这是因为在选择时，如果跳过了某个下标 $i$，那么在选择完毕后，将其中的最高分替换成 $\textit{nums}[i]$，最高分一定不会变大，与最低分的差值同样也不会变大。因此，一定存在有一种最优的选择方案，是连续选择了有序数组中的 $k$ 个连续的元素。

这样一来，我们首先对数组 $\textit{nums}$ 进行升序排序，随后使用一个大小固定为 $k$ 的滑动窗口在 $\textit{nums}$ 上进行遍历。记滑动窗口的左边界为 $i$，那么右边界即为 $i+k-1$，窗口中的 $k$ 名学生最高分和最低分的差值即为 $\textit{nums}[i+k-1] - \textit{nums}[i]$。

最终的答案即为所有 $\textit{nums}[i+k-1] - \textit{nums}[i]$ 中的最小值。

代码

###C++

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

###C#

public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        int n = nums.Length;
        Array.Sort(nums);
        int ans = int.MaxValue;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.Min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

###Python

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

###C

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int cmp(const void * pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

int minimumDifference(int* nums, int numsSize, int k){
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = INT_MAX;
    for (int i = 0; i + k - 1 < numsSize; ++i) {
        ans = MIN(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
}

###JavaScript

var minimumDifference = function(nums, k) {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let ans = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < n - k + 1; i++) {
        ans = Math.min(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
};

###go

func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    ans := math.MaxInt32
    for i, num := range nums[:len(nums)-k+1] {
        ans = min(ans, nums[i+k-1]-num)
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。排序需要的时间为 $O(n \log n)$，后续遍历需要的时间为 $O(n)$。
空间复杂度：$O(\log n)$，即为排序需要使用的栈空间。

数组中最大数对和的最小值

LeetCode 每日一题题解

LeetCode-Solution

2021年5月30日 00:16

方法一：排序 + 贪心

提示 $1$

数组内只有两个数的情况是平凡的。我们可以考虑数组中只有四个数 $x_1 \le x_2 \le x_3 \le x_4$ 的情况。此时 $(x_1, x_4), (x_2, x_3)$ 的拆分方法对应的最大数对和一定是最小的。

提示 $1$ 解释

我们可以枚举所有的拆分方法。除了上文的拆分方法外还有两种拆分方法：

$(x_1, x_3), (x_2, x_4)$

此时 $x_2 + x_4 \ge x_1 + x_4$ 且 $x_2 + x_4 \ge x_2 + x_3$。

那么 $\max(x_1+x_3,x_2+x_4) \ge x_2 + x_4 \ge \max(x_1+x_4,x_2+x_3)$。
$(x_1, x_2), (x_3, x_4)$

同样地，$\max(x_1+x_2,x_3+x_4) \ge x_3 + x_4 \ge \max(x_1+x_4,x_2+x_3)$。

提示 $2$

对于 $n$ 个数（$n$ 为偶数）的情况，上述的条件对应的拆分方法，即第 $k$ 大与第 $k$ 小组成的 $n / 2$ 个数对，同样可以使得最大数对和最小。

提示 $2$ 解释

我们可以类似 提示 $1$ 对所有数建立全序关系，即 $x_1 \le \cdots \le x_n$。我们需要证明，任意的拆分方法得到的最大数对和一定大于等于给定的拆分方法得到的最大数对和。

我们可以考虑上述命题的充分条件：假设给定拆分方法中的数对和 $x_k + x_{n+1-k}$ 在 $k = k'$ 时最大，那么对于任意的拆分方法，都存在一组 $u, v$ 使得 $x_u + x_v \ge x_{k'} + x_{n+1-k'}$。

我们可以用反证法证明。

同样，我们假设 $u < v$，那么使得 $x_v \ge x_{n+1-k'}$ 的 $v$ 的取值一共有 $k'$ 种。即闭区间 $[n+1-k',n]$ 中的所有整数。对于这些 $v$ 组成的数对，如果想使得 $x_u + x_v < x_{k'} + x_{n+1-k'}$ 恒成立，必须要 $x_u < x_{k'}$。此时需要有 $k'$ 个不同的 $u$ 的取值，但只有闭区间 $[1,k'-1]$ 中的 $k'-1$ 个整数满足 $x_u < x_{k'}$ 的条件，这就产生了矛盾。

因此，一定存在一组 $u, v$ 使得 $x_u + x_v \ge x_{k'} + x_{n+1-k'}$。