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 <= 100
• nums.length % 2 == 0
• 1 <= nums[i] <= 100

代码以及解题思路

代码

bool isPossibleToSplit(int* nums, int numsSize) {
    int count[101] = {0};
    for (int i = 0; i < numsSize; i++) {
        if (++count[nums[i]] > 2) {
            return false;
        }
    }
    return true;

}

解题思路：

1. 初始化计数数组：
   • 首先，创建一个大小为 101 的数组 count，用于记录 nums 中每个数字出现的次数。数组大小为 101 是因为题目没有明确数组 nums 中数字的范围，但通常假设在 0 到 100 之间（这是一个常见的假设，基于题目给出的 count 数组大小）。如果数字范围可能超过 100，则需要相应地调整 count 数组的大小。
   • 将 count 数组的所有元素初始化为 0，表示开始时没有任何数字出现过。
2. 统计数字出现次数：
   • 遍历数组 nums，对于每个元素 nums[i]，将其对应的 count[nums[i]] 值加 1。这表示每遇到一个数字，就在 count 数组中对应位置上加 1，以此统计每个数字的出现次数。
   • 在遍历过程中，如果发现任何一个数字的出现次数大于 2 (count[nums[i]] > 2)，则直接返回 false。因为这意味着至少有一个数字出现了三次或更多次，无法满足将数组分割成两个不包含相同数字的子集的条件。
3. 判断是否可以分割：
   • 如果遍历完整个数组 nums 后，没有发现任何数字的出现次数超过 2，则说明可以将数组 nums 分割成两个子集。每个子集中最多只包含每个数字的一个或两个实例（但由于每个数字最多只能在一个子集中出现，所以实际上每个数字要么在第一个子集中，要么在第二个子集中，或者根本不在任何子集中）。
   • 在这种情况下，返回 true，表示可以分割。

总结：

• 该代码的核心思想是通过统计每个数字的出现次数，判断是否存在数字出现次数超过 2，从而确定是否可以将数组 nums 分割成两个不包含相同数字的子集。
• 这种方法的时间复杂度是 O(n)，其中 n 是数组 nums 的长度，因为我们只需要遍历一次数组。空间复杂度是 O(1)（或 O(k)，其中 k 是数字可能的范围大小，这里假设为 101），因为我们使用了一个固定大小的数组来记录数字的出现次数。