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(len(nums))$
• 空间复杂度$O(len(nums))$

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 Counter

class 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 main

func isPossibleToSplit(nums []int) bool {
    times := map[int]int{}
    for _, n := range nums {
        times[n]++
        if (times[n] > 2) {
            return false
        }
    }
    return true
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/144789679