代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个下标从 0 开始的正整数数组 nums
。
你可以对数组执行以下两种操作 任意次 :
请你返回使数组为空的 最少 操作次数,如果无法达成,请返回 -1
。
示例 1:
输入:nums = [2,3,3,2,2,4,2,3,4] 输出:4 解释:我们可以执行以下操作使数组为空: - 对下标为 0 和 3 的元素执行第一种操作,得到 nums = [3,3,2,4,2,3,4] 。 - 对下标为 2 和 4 的元素执行第一种操作,得到 nums = [3,3,4,3,4] 。 - 对下标为 0 ,1 和 3 的元素执行第二种操作,得到 nums = [4,4] 。 - 对下标为 0 和 1 的元素执行第一种操作,得到 nums = [] 。 至少需要 4 步操作使数组为空。
示例 2:
输入:nums = [2,1,2,2,3,3] 输出:-1 解释:无法使数组为空。
提示:
2 <= nums.length <= 105
1 <= nums[i] <= 106
我们用一个哈希表 $count$ 统计数组中每个元素出现的次数,然后遍历哈希表,对于每个元素 $x$,如果 $x$ 出现的次数为 $c$,那么我们可以进行 $\lfloor \frac{c+2}{3} \rfloor$ 次操作,将 $x$ 删除,最后我们返回所有元素的操作次数之和即可。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 是数组的长度。
class Solution:
def minOperations(self, nums: List[int]) -> int:
count = Counter(nums)
ans = 0
for c in count.values():
if c == 1:
return -1
ans += (c + 2) // 3
return ans
class Solution {
public int minOperations(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
// count.put(num, count.getOrDefault(num, 0) + 1);
count.merge(num, 1, Integer::sum);
}
int ans = 0;
for (int c : count.values()) {
if (c < 2) {
return -1;
}
int r = c % 3;
int d = c / 3;
switch (r) {
case (0) -> {
ans += d;
}
default -> {
ans += d + 1;
}
}
}
return ans;
}
}
class Solution {
public:
int minOperations(vector<int>& nums) {
unordered_map<int, int> count;
for (int num : nums) {
++count[num];
}
int ans = 0;
for (auto& [_, c] : count) {
if (c < 2) {
return -1;
}
ans += (c + 2) / 3;
}
return ans;
}
};
func minOperations(nums []int) (ans int) {
count := map[int]int{}
for _, num := range nums {
count[num]++
}
for _, c := range count {
if c < 2 {
return -1
}
ans += (c + 2) / 3
}
return
}
function minOperations(nums: number[]): number {
const count: Map<number, number> = new Map();
for (const num of nums) {
count.set(num, (count.get(num) ?? 0) + 1);
}
let ans = 0;
for (const [_, c] of count) {
if (c < 2) {
return -1;
}
ans += ((c + 2) / 3) | 0;
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。