跳转至

3634. 使数组平衡的最少移除数目

题目描述

给你一个整数数组 nums 和一个整数 k。

如果一个数组的 最大 元素的值 至多 是其 最小 元素的 k 倍，则该数组被称为是 平衡 的。

你可以从 nums 中移除 任意 数量的元素，但不能使其变为 空 数组。

返回为了使剩余数组平衡，需要移除的元素的 最小 数量。

注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

 

示例 1:

输入：nums = [2,1,5], k = 2

输出：1

解释：

  • 移除 nums[2] = 5 得到 nums = [2, 1]。
  • 现在 max = 2, min = 1，且 max <= min * k，因为 2 <= 1 * 2。因此，答案是 1。

示例 2:

输入：nums = [1,6,2,9], k = 3

输出：2

解释：

  • 移除 nums[0] = 1 和 nums[3] = 9 得到 nums = [6, 2]。
  • 现在 max = 6, min = 2，且 max <= min * k，因为 6 <= 2 * 3。因此，答案是 2。

示例 3:

输入：nums = [4,6], k = 2

输出：0

解释：

  • 由于 nums 已经平衡，因为 6 <= 4 * 2，所以不需要移除任何元素。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 105

解法

方法一：排序 + 二分查找

我们首先对数组进行排序，然后我们从小到大枚举每个元素 \(\textit{nums}[i]\) 作为平衡数组的最小值，那么平衡数组的最大值 \(\textit{max}\) 必须满足 \(\textit{max} \leq \textit{nums}[i] \times k\)。因此，我们可以使用二分查找来找到第一个大于 \(\textit{nums}[i] \times k\) 的元素的下标 \(j\)，那么此时平衡数组的长度为 \(j - i\)，我们记录下最大的长度 \(\textit{cnt}\)，最后的答案就是数组长度减去 \(\textit{cnt}\)。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

1
2
3
4
5
6
7
8
class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()
        cnt = 0
        for i, x in enumerate(nums):
            j = bisect_right(nums, k * x)
            cnt = max(cnt, j - i)
        return len(nums) - cnt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int minRemoval(int[] nums, int k) {
        Arrays.sort(nums);
        int cnt = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int j = n;
            if (1L * nums[i] * k <= nums[n - 1]) {
                j = Arrays.binarySearch(nums, nums[i] * k + 1);
                j = j < 0 ? -j - 1 : j;
            }
            cnt = Math.max(cnt, j - i);
        }
        return n - cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        ranges::sort(nums);
        int cnt = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int j = n;
            if (1LL * nums[i] * k <= nums[n - 1]) {
                j = upper_bound(nums.begin(), nums.end(), 1LL * nums[i] * k) - nums.begin();
            }
            cnt = max(cnt, j - i);
        }
        return n - cnt;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func minRemoval(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    cnt := 0
    for i := 0; i < n; i++ {
        j := n
        if int64(nums[i])*int64(k) <= int64(nums[n-1]) {
            target := int64(nums[i])*int64(k) + 1
            j = sort.Search(n, func(x int) bool {
                return int64(nums[x]) >= target
            })
        }
        cnt = max(cnt, j-i)
    }
    return n - cnt
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function minRemoval(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
        let j = n;
        if (nums[i] * k <= nums[n - 1]) {
            const target = nums[i] * k + 1;
            j = _.sortedIndexBy(nums, target, x => x);
        }
        cnt = Math.max(cnt, j - i);
    }
    return n - cnt;
}

评论