class Solution {
public:
int maxSelectedElements(vector<int>& nums) {
}
};
100205. 修改数组后最大化数组中的连续元素数目
给你一个下标从 0 开始只包含 正 整数的数组 nums 。
一开始，你可以将数组中 任意数量 元素增加 至多 1 。
修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。
请你返回 最多 可以选出的元素数目。
示例 1：
输入：nums = [2,1,5,1,1] 输出：3 解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。 我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。 最多可以得到 3 个连续元素。
示例 2：
输入：nums = [1,4,7,10] 输出：1 解释：我们可以选择的最多元素数目是 1 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 106原站题解
java 解法, 执行用时: 94 ms, 内存消耗: 63.1 MB, 提交时间: 2024-02-19 14:49:43
class Solution {
public int maxSelectedElements(int[] nums) {
Arrays.sort(nums);
Map<Integer, Integer> f = new HashMap<>();
for (int x : nums) {
f.put(x + 1, f.getOrDefault(x, 0) + 1);
f.put(x, f.getOrDefault(x - 1, 0) + 1);
}
int ans = 0;
for (int res : f.values()) {
ans = Math.max(ans, res);
}
return ans;
}
}
golang 解法, 执行用时: 193 ms, 内存消耗: 19.8 MB, 提交时间: 2024-02-19 14:48:50
func maxSelectedElements(nums []int) (ans int) {
slices.Sort(nums) // 排序
f := map[int]int{}
for _, x := range nums {
f[x+1] = f[x] + 1
f[x] = f[x-1] + 1
}
for _, res := range f {
ans = max(ans, res)
}
return
}
python3 解法, 执行用时: 276 ms, 内存消耗: 48.9 MB, 提交时间: 2024-02-19 14:46:39
class Solution:
def maxSelectedElements(self, nums: List[int]) -> int:
nums.sort()
f = defaultdict(int)
for x in nums:
f[x + 1] = f[x] + 1
f[x] = f[x - 1] + 1
return max(f.values())