甘肃建设厅官方网站,wordpress官网视频教程,flashfxp链接网站,影视广告设计制作文章目录 Tag题目来源解题思路方法一#xff1a;贪心排序 写在最后 Tag
【贪心排序】【数组】【2024-02-02】 题目来源
1686. 石子游戏 VI 解题思路
方法一#xff1a;贪心排序
思路
假设有两个石子 i 和 j#xff0c;Alice 和 Bob 认为它们的价值分别为 a i a_i ai… 文章目录 Tag题目来源解题思路方法一贪心排序 写在最后 Tag
【贪心排序】【数组】【2024-02-02】 题目来源
1686. 石子游戏 VI 解题思路
方法一贪心排序
思路
假设有两个石子 i 和 jAlice 和 Bob 认为它们的价值分别为 a i a_i ai b i b_i bi 和 a j a_j aj b j b_j bj即 a l i c e V a l u e s [ a i , a j ] aliceValues [a_i, a_j] aliceValues[ai,aj] b o b V a l u e s [ b i , b j ] bobValues [b_i, b_j] bobValues[bi,bj]。
如果 Alice 取了石子 iBob 取了石子 j则它们的分差为 a i − b j a_i - b_j ai−bj如果 Alice 取了石子 jBob 取了石子 i则它们的分差为 a j − b i a_j - b_i aj−bi。对于 Alice这两个方案选择哪一种取决于这两个的分差 ( a i − b j ) − ( a j − b i ) ( a i b i ) − ( a j b j ) (a_i - b_j) - (a_j - b_i) (a_i b_i) - (a_j b_j) (ai−bj)−(aj−bi)(aibi)−(ajbj)。当这个值大于 0Alice 会优先选择石子 i当这个值小于 0 时Alice 会优先选择 j。因此Alice 在选择时会优先选择 ( a i b i ) (a_i b_i) (aibi) 大的石子。
实现中我们只需要将这两个数组 aliceValues 和 bobValues 对应元素相加后降序排序然后 Alice 和 Bob 依次选取然后计算两人的分数后进行比较返回结果。
算法
class Solution {
public:int stoneGameVI(vectorint aliceValues, vectorint bobValues) {int n aliceValues.size();vectortupleint, int, int values;for (int i 0; i n; i) {values.emplace_back(aliceValues[i] bobValues[i], aliceValues[i], bobValues[i]);}sort(values.begin(), values.end(), [](tupleint, int, inta, tupleint, int, intb) {return get0(a) get0(b);});int aliceSum 0, bobSum 0;for (int i 0; i n; i) {if (i 1) {bobSum get2(values[i]);}else {aliceSum get1(values[i]);}}if (aliceSum bobSum) {return 1;}else if (aliceSum bobSum) {return 0;}else {return -1;}}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) n n n 为数组的长度。
空间复杂度 O ( n ) O(n) O(n)为额外的数组 values 的大小。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
