从一个范围内选择最多整数 I
难度:
标签:
题目描述
You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:
- The chosen integers have to be in the range
[1, n]. - Each integer can be chosen at most once.
- The chosen integers should not be in the array
banned. - The sum of the chosen integers should not exceed
maxSum.
Return the maximum number of integers you can choose following the mentioned rules.
Example 1:
Input: banned = [1,6,5], n = 5, maxSum = 6 Output: 2 Explanation: You can choose the integers 2 and 4. 2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.
Example 2:
Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1 Output: 0 Explanation: You cannot choose any integer while following the mentioned conditions.
Example 3:
Input: banned = [11], n = 7, maxSum = 50 Output: 7 Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7. They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.
Constraints:
1 <= banned.length <= 1041 <= banned[i], n <= 1041 <= maxSum <= 109
代码结果
运行时间: 90 ms, 内存: 17.7 MB
// 思路：
// 1. 使用Java Stream生成1到n的数字流。
// 2. 过滤掉banned中的数字。
// 3. 在限制的maxSum内累加选择的数字，并统计数量。
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
import java.util.stream.IntStream;
public class Solution {
public int maxCount(int[] banned, int n, int maxSum) {
Set<Integer> bannedSet = new HashSet<>(Arrays.asList(Arrays.stream(banned).boxed().toArray(Integer[]::new)));
int[] sum = {0};
return (int) IntStream.rangeClosed(1, n)
.filter(i -> !bannedSet.contains(i) && (sum[0] += i) <= maxSum)
.count();
}
}
解释
方法:
这道题的思路是贪心算法。首先，将banned数组转换为集合s，便于快速查询某个整数是否被禁止。然后，从1开始遍历到n，对于每一个整数i，如果i不在s中且i小于等于maxSum，那么就将i加入到选择中，并且从maxSum中减去i，同时增加选择的整数数量ans。遍历结束后，ans即为最多可以选择的整数数目。
时间复杂度:
O(n)
空间复杂度:
O(banned.length)
代码细节讲解
🦆
为什么选择将banned数组转换为集合而不是其他数据结构，如列表或字典？
▷🦆
在遍历整数时，如果当前整数i大于maxSum就立即停止遍历，这种方法是否可能错过一些有效的选择？例如，如果后面的数字较小且未被禁止，是否还有机会继续选择？
▷🦆
具体是如何保证这种贪心算法选择的整数数目是最大可能的？是否存在证明或是特定的逻辑来支持这一点？
▷🦆
算法中没有显式处理所有banned元素都在[1, n]范围外的情况，这是否会影响算法的准确性或效率？
▷