3046. Split the Array

Problem

You are given an integer array nums of even length. You have to split the array into two parts nums1 and nums2 such that:

• nums1.length == nums2.length == nums.length / 2.
• nums1 should contain distinct elements.
• nums2 should also contain distinct elements.

Return true if it is possible to split the array, and false otherwise.

https://leetcode.cn/problems/split-the-array/

Example 1:

Input: nums = [1,1,2,2,3,4]
Output: true
Explanation: One of the possible ways to split nums is nums1 = [1,2,3] and nums2 = [1,2,4].

Example 2:

Input: nums = [1,1,1,1]
Output: false
Explanation: The only possible way to split nums is nums1 = [1,1] and nums2 = [1,1]. Both nums1 and nums2 do not contain distinct elements. Therefore, we return false.

Constraints:

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

Test Cases

1
2

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([1,1,2,2,3,4], True),
    ([1,1,1,1], False),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    assert sol.isPossibleToSplit(nums) == expected

Thoughts

扫描数组，用字典记录每一个数字的次数，如果任何一个数字的次数超过 2 就返回 false。

可以用 Python 自带的 collections.Counter。但如果自己写循环处理，有可能更早地发现无法拆分，能节省一些时间。

Code

1
2
3
4
5
6
7
8
9
10
11
12

from collections import defaultdict


class Solution:
    def isPossibleToSplit(self, nums: list[int]) -> bool:
        occurs: dict[int, int] = defaultdict(int) # {num, freq}
        for num in nums:
            occurs[num] += 1
            if occurs[num] > 2:
                return False

        return True

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章