⚖️ 初学者友好指南 “Minimum Removals to Balance Array” - 题目 3634 (C++, Python, JavaScript)

Source: Dev.to

请提供您希望翻译的具体文本内容，我会按照要求保留源链接、格式和代码块，仅翻译正文部分为简体中文。

问题概述

给定：

• 一个整数数组 nums。
• 一个整数 k，表示最大允许的最大元素与最小元素的比例。

你的目标是计算需要删除的最少元素数量，以使数组达到平衡。数组平衡的条件是

[ \frac{\text{max}}{\text{min}} \le k ]

直觉：排序的力量

为了满足涉及最小值和最大值的条件，第一步是对数组进行排序。在已排序的数组中，任何连续子数组（切片）的第一个元素是最小值，最后一个元素是最大值。

该解法使用贪心的“双指针”或“滑动窗口”方法。
将某个元素固定为最小值，并在条件满足的情况下尽可能多地包含后续元素。

在遍历已排序的数组时，我们维护一个从索引 i 开始的“有效窗口”。如果当前元素 a 超过了基于 A[i] 的允许上限，我们通过递增 i 来实际“移除”一个元素。由于我们希望最少移除元素，因此在寻找能够保留的最大元素数量。

步骤演示：理解示例

示例： nums = [1, 6, 2, 9], k = 3

1. 对数组进行排序 → [1, 2, 6, 9]。
2. 初始化 i = 0。
3. 迭代：
   • a = 1 → 1 ≤ 1·3 → 窗口 [1]，i 保持为 0。
   • a = 2 → 2 ≤ 1·3 → 窗口 [1, 2]，i 保持为 0。
   • a = 6 → 6 > 1·3 → 将 i 增加到 1。
   • a = 9 → 与新的最小值 2 比较：9 > 2·3 → 将 i 增加到 2。

最终的 i 值为 2，这意味着我们需要删除 2 个元素以得到一个平衡数组。

代码实现

C++

class Solution {
public:
    int minRemoval(vector<int>& A, int k) {
        // Sort to easily identify min and max in any range
        sort(A.begin(), A.end());
        int i = 0;
        for (int a : A) {
            // If current element is too large for the current min at A[i]
            // we increment i, effectively shrinking the 'kept' count
            if (a > 1LL * A[i] * k) {
                i++;
            }
        }
        return i;
    }
};

Python

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        # Sort the numbers to maintain a sliding window of valid elements
        nums.sort()
        i = 0
        for a in nums:
            # If the current max (a) exceeds min (nums[i]) * k, we must remove an element
            if a > nums[i] * k:
                i += 1
        return i

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minRemoval = function(nums, k) {
    // Sort numerically as JS default sort is lexicographical
    nums.sort((a, b) => a - b);
    let i = 0;
    for (let a of nums) {
        // Check if the current element violates the balance condition
        if (a > nums[i] * k) {
            i++;
        }
    }
    return i;
};

关键要点

• 作为预处理的排序： 当问题提到“最小值”和“最大值”约束时，排序通常可以将搜索空间从 (O(n^2)) 降低到 (O(n))。
• 滑动窗口逻辑： 保持指针 i 可以跟踪有效范围的起始位置，并计算有多少元素超出该范围。
• 整数溢出： 在 C++ 中，两个大整数相乘可能会超出 int 的限制。使用 1LL（long long）可确保乘法安全进行。

Final Thoughts

这个问题展示了在现实系统中如何定义“平衡”状态。在服务器的负载均衡或金融投资组合风险管理中，我们常常需要确保没有单一实体相对于其他实体过于庞大，以防止系统故障或波动。掌握这种滑动窗口逻辑有助于你构建保持在安全运行参数范围内的系统。