将玩家分成技能相同的团队

2491。将玩家分成技能相同的小组

难度：中等

主题：数组、哈希表、两个指针、排序

您将获得一个偶数长度n的正整数数组技能，其中skill[i]表示第i^第个玩家的技能。将玩家分为 n / 2 个规模为 2 的团队，使得每个团队的总技能相等。

一支球队的化学反应等于该球队球员技能的乘积。

返回所有球队化学反应的总和，或者如果无法将球员分成几队以使每队总技能相等则返回-1.

示例1：

• 输入：技能= [3,2,5,1,3,4]
• 输出： 22
• 说明：
  • 将玩家分为以下几队：(1, 5), (2, 4), (3, 3)，每队的总技能为 6。
  • 所有队伍的化学反应总和为：1 * 5 2 * 4 3 * 3 = 5 8 9 = 22。

示例2：

• 输入：技能= [3,4]
• 输出： 112
• 说明：
  • 两名玩家组成一队，总技能为7。
  • 团队的化学反应是3 * 4 = 12。

示例 3：

• 输入：技能= [1,1,2,3]
• 输出： -1
• 说明：没有办法将玩家分成几队以使每队的总技能相等。

约束：

• 2 5
• 技能.长度是偶数。
• 1

提示：

1. 尝试对技能数组进行排序。
2. 将最弱的可用玩家与最强的可用玩家配对始终是最佳选择。

解决方案：

我们可以按照提供的提示并使用贪心方法。以下是解决方案的详细分解：

步骤：

1. 对技能数组进行排序：排序使我们能够有效地将最弱的玩家（最小值）与最强的玩家（最大值）配对。

2. 检查有效配对：每个团队的技能总和应该相等。排序后，我们将最小和最大的元素配对，然后将第二小的元素与第二大的元素配对，依此类推。如果在任何时候，一对的总和与之前的总和不同，则不可能将玩家分为有效的团队，我们应该返回 -1。

3. 计算化学反应：每个团队的化学反应是该团队中两种技能的乘积。总结每个有效团队的所有化学反应值。

4. 返回总化学反应：如果所有队伍的总技能相同，则返回他们的化学反应总和。

让我们用 PHP 实现这个解决方案：2491。将玩家分成技能相同的小组

<p><?php<br>
/**</p>

<ul>
<li>@param Integer[] $skill</li>
<li>@return Integer
<em>/
function dividePlayers($skill) {
...
...
...
/</em>*

<ul>
<li>go to ./solution.php
*/
}
</li>
</ul>
</li>
</ul>

<p>// Test cases<br>
$skill1 = [3, 2, 5, 1, 3, 4];<br>
$skill2 = [3, 4];<br>
$skill3 = [1, 1, 2, 3];</p>

<p>echo dividePlayers($skill1) . "\n";  // Output: 22<br>
echo dividePlayers($skill2) . "\n";  // Output: 12<br>
echo dividePlayers($skill3) . "\n";  // Output: -1<br>
?></p>

说明：

1. 排序：数组技能排序，保证我们能够高效地将最小值和最大值配对。

2. 两个指针：我们使用两个指针（$i 从开头开始，$j 从结尾开始）。对于每个有效对（最小和最大），我们检查它们的总和是否与预期的 teamSkillSum 相同。如果没有的话，就不可能将玩家分队。

3. 化学计算：如果该对有效，则化学计算为两个值的乘积 ($skill[$i] * $skill[$j])，并且我们继续将其添加到总化学中。

4. 边缘情况：

   • 如果由于金额不等而无法组队，我们返回-1。
   • 代码处理长度均匀的情况，并确保所有玩家正确配对。

时间复杂度：

• 对数组进行排序需要 O(n log n)，两指针遍历需要 O(n)。因此，总体时间复杂度为 O(n log n)，在给定约束的情况下，这是有效的。

此解决方案在最多 10⁵ 名玩家的给定限制内有效。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是将玩家分成技能相同的团队的详细内容。更多信息请关注PHP中文网其他相关文章！