LeetCode 3046.分割数组：计数

2025/4/30 12:23:47 来源：https://blog.csdn.net/Tisfy/article/details/144789679 浏览: 次关键词：LeetCode 3046.分割数组：计数

【LetMeFly】3046.分割数组：计数

力扣题目链接：https://leetcode.cn/problems/split-the-array/

给你一个长度为偶数的整数数组 nums 。你需要将这个数组分割成 nums1 和 nums2 两部分，要求：

nums1.length == nums2.length == nums.length / 2 。
nums1 应包含 互不相同 的元素。
nums2也应包含 互不相同 的元素。

如果能够分割数组就返回 true ，否则返回 false 。

示例 1：

输入：nums = [1,1,2,2,3,4]
输出：true
解释：分割 nums 的可行方案之一是 nums1 = [1,2,3] 和 nums2 = [1,2,4] 。

示例 2：

输入：nums = [1,1,1,1]
输出：false
解释：分割 nums 的唯一可行方案是 nums1 = [1,1] 和 nums2 = [1,1] 。但 nums1 和 nums2 都不是由互不相同的元素构成。因此，返回 false 。

提示：

1 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

解题方法：哈希表计数

使用哈希表统计每个数出现的次数，一旦有数字出现3次及以上就直接返回false。

所有数字都出现2次及一下则返回true。

时间复杂度 $O (l e n (n u m s))$
空间复杂度 $O (l e n (n u m s))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2024-12-28 14:38:57* @LastEditors: LetMeFly.xyz* @LastEditTime: 2024-12-28 14:40:14*/
class Solution {
public:bool isPossibleToSplit(vector<int>& nums) {int times[101] = {0};for (int t : nums) {times[t]++;if (times[t] > 2) {return false;}}return true;}
};

Python

'''
Author: LetMeFly
Date: 2024-12-28 14:40:34
LastEditors: LetMeFly.xyz
LastEditTime: 2024-12-28 14:41:10
'''
from typing import List
from collections import Counterclass Solution:def isPossibleToSplit(self, nums: List[int]) -> bool:return max(Counter(nums).values()) <= 2

Java

/** @Author: LetMeFly* @Date: 2024-12-28 14:43:42* @LastEditors: LetMeFly.xyz* @LastEditTime: 2024-12-28 14:45:25*/
import java.util.HashMap;class Solution {public boolean isPossibleToSplit(int[] nums) {HashMap<Integer, Integer> times = new HashMap<>();for (int t : nums) {if (times.merge(t, 1, Integer::sum) > 2) {return false;}}return true;}
}

Go

/** @Author: LetMeFly* @Date: 2024-12-28 14:48:56* @LastEditors: LetMeFly.xyz* @LastEditTime: 2024-12-28 14:57:51*/
package mainfunc isPossibleToSplit(nums []int) bool {times := map[int]int{}for _, n := range nums {times[n]++if (times[n] > 2) {return false}}return true
}