题目

题目链接🔗
给你一个长度为 偶数 的整数数组 $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. $1\le nums.length\le 100$
2. $nums.length$
3. $1\le nums[i]\le 100$

思路

要将数组 nums 分割成两个长度相等且元素互不相同的子数组 nums1 和 nums2，直接看出现次数最多的元素有多少个，如果次数大于二肯定分不了，否则一定能分的了。

代码

class Solution {
public:bool isPossibleToSplit(vector<int>& nums) {int arr[105]={0};memset(arr,0,105);int maxzhi=0;for(int i=0;i<nums.size();++i){arr[nums[i]]++;maxzhi=max(maxzhi,arr[nums[i]]);}if(maxzhi>2)return 0;return 1;}
};

复杂度分析

时间复杂度

遍历数组统计元素出现次数的时间复杂度为 $O(n)$

空间复杂度

$O(1)$

结果