[LeetCode] 每日一题 3046. 分割数组

题目链接

题目描述

给你一个长度为 偶数 的整数数组 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, queries.length <= 10^5

• 1 <= queries[i] <= 10^5

• 1 <= nums[i], x <= 10^4

题解

解题思路

我们只需要判断是否可以将数组分割为满足条件的两个子数组：

1. 每个数字最多只能出现两次。如果某个数字的频率超过 2，那么这个数字无法被均分到两个数组中

2. 利用哈希表统计每个数字的出现次数，如果存在某个数字的出现次数大于 2，则直接返回 false，否则返回 true

代码实现

class Solution {
    public boolean isPossibleToSplit(int[] nums) {
        // 使用哈希表统计每个数字的出现次数
        HashMap<Integer, Integer> cnt = new HashMap<>();
        for (int num : nums) {
            cnt.put(num, cnt.getOrDefault(num, 0) + 1);
            // 如果某个数字出现次数超过 2，直接返回 false
            if (cnt.get(num) > 2) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

1. 时间复杂度：

   • 遍历数组需要 O(n)，其中 n 是数组的长度。

   • 哈希表的插入和查找操作平均时间复杂度为 O(1)。

   • 总的时间复杂度为 O(n)。

2. 空间复杂度：

   • 哈希表的空间复杂度为 O(k)，其中 k 是数组中不同元素的数量。

   • 最坏情况下 k=n（所有元素都不同），空间复杂度为 O(n)。

总结

该题的关键在于利用哈希表统计数字出现的次数，并验证是否满足条件。整个过程简单高效，时间复杂度和空间复杂度都能满足需求。

通过本题，我们可以更深刻地理解如何运用哈希表处理频率统计问题，以及如何快速判断条件是否成立。这种解法不仅简洁，而且清晰地揭示了问题的本质。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。