力扣 429 场周赛-前两题
力扣 429 场周赛-前两题
3396. 使数组元素互不相同所需的最少操作次数
描述
给你一个整数数组 nums,你需要确保数组中的元素 互不相同 。为此,你可以执行以下操作任意次:
从数组的开头移除 3 个元素。如果数组中元素少于 3 个,则移除所有剩余元素。
注意:空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。
示例 1:
输入: nums = [1,2,3,4,2,3,3,5,7]
输出: 2
解释:
第一次操作:移除前 3 个元素,数组变为 [4, 2, 3, 3, 5, 7]。
第二次操作:再次移除前 3 个元素,数组变为 [3, 5, 7],此时数组中的元素互不相同。
因此,答案是 2。
示例 2:
输入: nums = [4,5,6,4,4]
输出: 2
解释:
第一次操作:移除前 3 个元素,数组变为 [4, 4]。
第二次操作:移除所有剩余元素,数组变为空。
因此,答案是 2。
示例 3:
输入: nums = [6,7,8,9]
输出: 0
解释:
数组中的元素已经互不相同,因此不需要进行任何操作,答案是 0。
提示:
1 <= nums.length <= 100
1 <= nums[i] <= 100
解答
/**
* @param {number[]} nums
* @return {number}
*/
var minimumOperations = function (nums) {
const set = new Set()
let i = nums.length - 1
while (!set.has(nums[i]) && i >= 0) {
if (i === 0) {
return 0
}
set.add(nums[i])
i -= 1
}
return Math.ceil((i + 1) / 3)
}
3397. 执行操作后不同元素的最大数量
描述
给你一个整数数组 nums 和一个整数 k。
你可以对数组中的每个元素 最多 执行 一次 以下操作:
将一个在范围 [-k, k] 内的整数加到该元素上。
返回执行这些操作后,nums 中可能拥有的不同元素的 最大 数量。
示例 1:
输入: nums = [1,2,2,3,3,4], k = 2
输出: 6
解释:
对前四个元素执行操作,nums 变为 [-1, 0, 1, 2, 3, 4],可以获得 6 个不同的元素。
示例 2:
输入: nums = [4,4,4,4], k = 1
输出: 3
解释:
对 nums[0] 加 -1,以及对 nums[1] 加 1,nums 变为 [3, 5, 4, 4],可以获得 3 个不同的元素。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 109
解答
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxDistinctElements = function (nums, k) {
nums.sort((x, y) => x - y)
let re = 0
let tK = k === 0 ? 0 : k * 2
nums.forEach((item, idx) => {
item = item - k
nums[idx] = item
if (idx !== 0 && item + tK <= nums[idx - 1]) {
nums[idx] = nums[idx - 1]
} else {
re += 1
if (idx !== 0 && item <= nums[idx - 1]) {
nums[idx] = nums[idx - 1] + 1
}
}
})
return re
}