题目描述
给你一个整数数组 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 <= 1051 <= nums[i] <= 1091 <= 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}\) 的长度。
| 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | impl Solution {
pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort();
let mut cnt = 0;
let n = nums.len();
for i in 0..n {
let mut j = n;
let target = nums[i] as i64 * k as i64;
if target <= nums[n - 1] as i64 {
j = nums.partition_point(|&x| x as i64 <= target);
}
cnt = cnt.max(j - i);
}
(n - cnt) as i32
}
}
|
方法二：排序 + 双指针
我们首先对数组进行排序，然后我们使用双指针来维护一个滑动窗口，左指针 \(l\) 从左到右枚举每个元素 \(\textit{nums}[l]\) 作为平衡数组的最小值，右指针 \(r\) 不断向右移动，直到 \(\textit{nums}[r]\) 大于 \(\textit{nums}[l] \times k\)，此时平衡数组的长度为 \(r - l\)，需要移除的元素数量为 \(n - (r - l)\)，我们记录下最小的移除数量作为答案。
时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。
| class Solution:
def minRemoval(self, nums: List[int], k: int) -> int:
nums.sort()
ans = n = len(nums)
r = 0
for l in range(n):
while r < n and nums[r] <= nums[l] * k:
r += 1
ans = min(ans, n - (r - l))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int minRemoval(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int ans = n;
int r = 0;
for (int l = 0; l < n; l++) {
while (r < n && nums[r] <= (long) nums[l] * k) {
r++;
}
ans = Math.min(ans, n - (r - l));
}
return ans;
}
}
|
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 n = nums.size();
int ans = n;
int r = 0;
for (int l = 0; l < n; l++) {
while (r < n && nums[r] <= (long long) nums[l] * k) {
r++;
}
ans = min(ans, n - (r - l));
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func minRemoval(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
ans := n
r := 0
for l := 0; l < n; l++ {
for r < n && nums[r] <= nums[l]*k {
r++
}
ans = min(ans, n-(r-l))
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function minRemoval(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let ans = n;
let r = 0;
for (let l = 0; l < n; l++) {
while (r < n && nums[r] <= nums[l] * k) {
r++;
}
ans = Math.min(ans, n - (r - l));
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | impl Solution {
pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort();
let n = nums.len();
let mut ans = n;
let mut r = 0;
let k = k as i64;
for l in 0..n {
while r < n && nums[r] as i64 <= nums[l] as i64 * k {
r += 1;
}
ans = ans.min(n - (r - l));
}
ans as i32
}
}
|