2491-划分技能点相等的团队

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

给你一个正整数数组 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

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

方法一：排序

如果最小的不和最大的匹配，那么最大的和一个比最小数更大的数匹配，就会导致技能点之和不相等。

因此最小的一定和最大的匹配。

那么排序后模拟即可。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        ans, s = 0, skill[0] + skill[-1]
        for i in range(len(skill) // 2):
            x, y = skill[i], skill[-1 - i]
            if x + y != s: return -1
            ans += x * y
        return ans
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
func dividePlayers(skill []int) (ans int64) {
	sort.Ints(skill)
	n := len(skill)
	sum := skill[0] + skill[n-1]
	for i := 0; i < n/2; i++ {
		x, y := skill[i], skill[n-1-i]
		if x+y != sum {
			return -1
		}
		ans += int64(x * y)
	}
	return
}

复杂度分析

  • 时间复杂度：O(n\log n)，其中 n 为 skill 的长度。
  • 空间复杂度：O(1)，忽略排序的栈空间，只用到若干额外变量。

方法二：哈希表

设 total 为 skill 所有数之和，m 为 skill 长度的一半。

那么 total 必须为 m 的倍数，否则返回 -1。

统计 skill 每个数的出现次数，记在哈希表 cnt 中。

设 s=\dfrac{\textit{total} }{m，遍历哈希表，如果 cnt}[x]\ne cnt[s-x]，则无法匹配，返回 -1。

否则把 cnt}[x]\cdot x\cdot(s-x) 记到答案中。

最后返回答案的一半（因为重复记录了对称的部分）。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        total, m = sum(skill), len(skill) // 2
        if total % m: return -1
        ans, s = 0, total // m
        cnt = Counter(skill)
        for x, c in cnt.items():
            if c != cnt[s - x]: return -1
            ans += c * x * (s - x)
        return ans // 2
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func dividePlayers(skill []int) (ans int64) {
	total := 0
	cnt := map[int]int{}
	for _, x := range skill {
		total += x
		cnt[x]++
	}
	m := len(skill) / 2
	if total%m > 0 {
		return -1
	}
	s := total / m
	for x, c := range cnt {
		if c != cnt[s-x] {
			return -1
		}
		ans += int64(c * x * (s - x))
	}
	return ans / 2
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 skill 的长度。
  • 空间复杂度：O(n)。
 Comments
On this page
2491-划分技能点相等的团队
  1. 方法一：排序
  2. 方法二：哈希表