プレイヤーを同じスキルのチームに分ける

2491。プレイヤーを同じスキルのチームに分けます

難易度: 中

トピック: 配列、ハッシュ テーブル、2 つのポインター、ソート

あなたには、長さ n が 偶数 の正の整数配列スキルが与えられます。ここで、skill[i] は i ^番目 のプレイヤーのスキルを示します。各チームの合計スキルが 等しくなるように、プレーヤーをサイズ 2 の n / 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
• 説明:
  • 2 人のプレイヤーは合計スキル 7 のチームを形成します。
  • チームの相性は 3 * 4 = 12 です。

例 3:

• 入力: スキル = [1,1,2,3]
• 出力: -1
• 説明: 各チームの合計スキルが等しくなるようにプレーヤーをチームに分ける方法はありません。

制約:

• 2 105
skill.length は偶数です。
1

ヒント:

スキル配列を並べ替えてみます。
利用可能な最も弱いプレーヤーと最も強いプレーヤーをペアにすることが常に最適です。

解決策:

提供されたヒントに従い、貪欲なアプローチを使用できます。ソリューションの詳細な内訳は次のとおりです:

手順:

1. スキル配列を並べ替えます

   : 並べ替えにより、最も弱いプレーヤー (最小値) と最も強いプレーヤー (最大値) を効率的に組み合わせることができます。

2. 有効なペアリングをチェック

   : 各チームのスキルの合計は等しい必要があります。並べ替えた後、最小の要素と最大の要素をペアにし、次に 2 番目に小さい要素と 2 番目に大きい要素を組み合わせます。いずれかの時点でペアの合計が以前の合計と異なる場合は、プレーヤーを有効なチームに分割することは不可能であるため、-1 を返す必要があります。

3. 化学反応を計算する: 各チームの化学反応は、そのチームの 2 つのスキルの積です。有効な各チームのすべての化学値を合計します。

4. 合計ケミストリーを返します: すべてのチームが同じ合計スキルを持っている場合、チームのケミストリーの合計を返します。

このソリューションを PHP で実装してみましょう: 2491。プレイヤーを同じスキルのチームに分けます

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

• @param Integer[] $skill
• @return Integer / function dividePlayers($skill) { ... ... ... /*
  • go to ./solution.php */ }

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

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

説明:

1. ソート: 配列スキルは、最小値と最大値を効率的にペアリングできるようにソートされます。

2. 2 つのポインター: 2 つのポインター (先頭から始まる $i と末尾から始まる $j) を使用します。有効なペア (最小値と最大値) ごとに、それらの合計が予想されるteamSkillSumと同じかどうかを確認します。そうしないと、選手をチームに分けることができません。

3. 化学計算: ペアが有効な場合、化学は 2 つの値 ($skill[$i] * $skill[$j]) の積として計算されます。トータルケミストリーにそれを加え続けてください。

4. エッジケース:

   • 合計が等しくないためにチームを編成できない場合は、-1 を返します。
   • このコードは、均等な長さのケースを処理し、すべてのプレーヤーが正しくペアリングされるようにします。

時間計算量:

• 配列のソートには O(n log n) がかかり、2 ポインターの走査には O(n) がかかります。したがって、全体的な時間計算量は O(n log n) となり、制約を考慮すると効率的です。

このソリューションは、最大 10⁵ プレイヤーという指定された制約内で機能します。

連絡先リンク

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

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

• 领英
• GitHub

以上がプレイヤーを同じスキルのチームに分けるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。