划分技能点相等的团队

标签: 数组 哈希表 双指针 排序

难度: Medium

给你一个正整数数组 skill ，数组长度为 偶数 n ，其中 skill[i] 表示第 i 个玩家的技能点。将所有玩家分成 n / 2 个 2 人团队，使每一个团队的技能点之和 相等 。

团队的 化学反应 等于团队中玩家的技能点 乘积 。

返回所有团队的 化学反应 之和，如果无法使每个团队的技能点之和相等，则返回 -1 。

示例 1：

输入：skill = [3,2,5,1,3,4]
输出：22
解释：
将玩家分成 3 个团队 (1, 5), (2, 4), (3, 3) ，每个团队的技能点之和都是 6 。
所有团队的化学反应之和是 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22 。

示例 2：

输入：skill = [3,4]
输出：12
解释：
两个玩家形成一个团队，技能点之和是 7 。
团队的化学反应是 3 * 4 = 12 。

示例 3：

输入：skill = [1,1,2,3]
输出：-1
解释：
无法将玩家分成每个团队技能点都相等的若干个 2 人团队。

提示：

  • 2 <= skill.length <= 105
  • skill.length 是偶数
  • 1 <= skill[i] <= 1000

Submission

运行时间: 55 ms

内存: 26.3 MB

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        pairsum = skill[0] + skill[-1]
        reaction = skill[0] * skill[-1]
        for i in range(1, len(skill) // 2):
            if skill[i] + skill[-1 - i] != pairsum:
                return -1
            else:
                reaction += skill[i] * skill[-1 - i]
        return reaction

Explain

该题解通过先对技能点数组进行排序，然后尝试将最小的元素和最大的元素配对，第二小的元素与第二大的元素配对，以此类推，形成团队。这种配对方式旨在通过将极端值配对来平衡团队的技能点之和，以期望每个团队的技能点之和都相等。如果在配对过程中发现某一对的技能点之和与之前的不同，则返回-1，表明无法形成要求的团队。如果所有配对的技能点之和都相等，则计算每个团队的化学反应（即技能点的乘积），并计算总和返回。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()  # 对技能点数组进行排序
        pairsum = skill[0] + skill[-1]  # 计算第一个和最后一个元素的和
        reaction = skill[0] * skill[-1]  # 计算第一个和最后一个元素的乘积
        for i in range(1, len(skill) // 2):  # 从第二对开始遍历至中间
            if skill[i] + skill[-1 - i] != pairsum:  # 检查当前配对的和是否与第一对相等
                return -1  # 如果不相等，返回-1
            else:
                reaction += skill[i] * skill[-1 - i]  # 累加乘积
        return reaction  # 返回所有团队的化学反应之和

Explore

排序然后配对数组的最小元素和最大元素的方法可以帮助平衡团队的技能点之和。通过这种方式，可以最大化地减少每对团队间技能点之和的差异，理论上更有可能达到所有团队技能点之和相等的目标。此外，排序后的配对策略可以简化问题，使得算法更易实现和理解。未排序的配对可能需要复杂的逻辑来确保所有团队的技能点之和相等，而且计算复杂度可能更高。

这种方法并不能保证所有团队的技能点之和总是相等。这种配对策略是一种启发式方法，它在某些情况下能够工作，尤其是当数组元素能够很好地互补时。然而，如果数组中的数值差异较大或分布不均，这种方法可能无法使所有团队的技能点之和相等。在这种情况下，算法会检测到不一致并返回-1，表示无法按要求分配团队。

是的，这种方法可能会忽略其他可能的配对方式。算法依赖于排序后的简单配对策略，即将最小的元素与最大的元素配对，这种方式在发现第一个不符合条件的配对时就会终止并返回-1。这意味着算法没有考虑重新排列或选择不同配对策略的可能性，可能存在其他的配对顺序可以满足所有团队技能点之和相等的条件。然而，探索所有可能的配对方式将大大增加算法的复杂性和执行时间。