目录
按⾝⾼排序（easy）
题目解析
讲解算法原理
编写代码
优势洗牌（⽥忌赛⻢）（medium）
题目解析
讲解算法原理
编写代码
按⾝⾼排序（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个字符串数组 names ，和⼀个由互不相同的正整数组成的数组 heights 。两个数组的⻓度均为 n 。
对于每个下标 i ， names[i] 和 heights[i] 表⽰第 i 个⼈的名字和⾝⾼。请按⾝⾼降序顺序返回对应的名字数组 names 。
⽰例1：
输⼊：names=["Mary","John","Emma"],heights=[180,165,170]
输出：["Mary","Emma","John"]
解释：Mary最⾼，接着是Emma和John。
⽰例2：
输⼊：names=["Alice","Bob","Bob"],heights=[155,185,150]
输出：["Bob","Alice","Bob"]
解释：第⼀个Bob最⾼，然后是Alice和第⼆个Bob。
提⽰：
◦ n == names.length == heights.length
◦ 1 <= n <= 10(3)
◦ 1 <= names[i].length <= 20
◦ 1 <= heights[i] <= 10(5)
◦ names[i] 由⼤⼩写英⽂字⺟组成
◦ heights 中的所有值互不相同
讲解算法原理
解法（通过排序''索引''的⽅式）：
算法思路：
我们不能直接按照 i 位置对应的 heights 来排序，因为排序过程是会移动元素的，但是
names 内的元素是不会移动的。
由题意可知， names 数组和 heights 数组的下标是⼀⼀对应的，因此我们可以重新创建出来⼀个下标数组，将这个下标数组按照 heights[i] 的⼤⼩排序。
那么，当下标数组排完序之后，⾥⾯的顺序就相当于 heights 这个数组排完序之后的下标。之后通过排序后的下标，依次找到原来的 name ，完成对名字的排序。
编写代码
c++算法代码：
class Solution
{
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {// 1. 创建⼀个下标数组int n = names.size();vector<int> index(n);for(int i = 0; i < n; i++) index[i] = i;// 2. 对下标进⾏排序sort(index.begin(), index.end(), [&](int i, int j){return heights[i] > heights[j];});// 3. 提取结果vector<string> ret;for(int i : index){ret.push_back(names[i]);}return ret;}
};java">class Solution
{public String[] sortPeople(String[] names, int[] heights) {// 1. 创建⼀个下标数组int n = names.length;Integer[] index = new Integer[n];for(int i = 0; i < n; i++) index[i] = i;// 2. 对下标数组排序Arrays.sort(index, (i, j) -> {return heights[j] - heights[i];});// 3. 提取结果String[] ret = new String[n];for(int i = 0; i < n; i++){ret[i] = names[index[i]];}return ret;}
}优势洗牌（⽥忌赛⻢）（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
注意注意注意！！！
做这道题之前建议先把2418.按⾝⾼排序⾥⾯，通过排序数组下标，进⽽不改变原数组顺序的排序技巧好好吸收消化掉。不然⾥⾯变量众多，很容易犯迷。
2.题目解析
给定两个⻓度相等的数组 nums1 和 nums2 ， nums1 相对于 nums2 的优势可以⽤满⾜
nums1[i] > nums2[i] 的索引 i 的数⽬来描述。
返回nums1的任意排列，使其相对于 nums2 的优势最⼤化。
⽰例1：
输⼊：nums1=[2,7,11,15],nums2=[1,10,4,11]
输出：[2,11,7,15]
⽰例2：
输⼊：nums1=[12,24,8,32],nums2=[13,25,32,11]
输出：[24,32,8,12]
提⽰：
◦ 1 <= nums1.length <= 10(5)
◦ nums2.length == nums1.length
◦ 0 <= nums1[i], nums2[i] <= 10(9)
讲解算法原理
解法（贪⼼）：
讲⼀下⽥忌赛⻢背后包含的博弈论和贪⼼策略：
⽥忌赛⻢没听过的⾃⾏百度，这⾥讲⼀下⽥忌赛⻢背后的博弈决策，从三匹⻢拓展到 n 匹⻢之间博弈的最优策略。
⽥忌：下等⻢中等⻢上等⻢
⻬王：下等⻢中等⻢上等⻢
a. ⽥忌的下等⻢ pk 不过⻬王的下等⻢，因此把这匹⻢丢去消耗⼀个⻬王的最强战⻢！b. 接下来选择中等⻢ pk ⻬王的下等⻢，勉强获胜；
c. 最后⽤上等⻢ pk ⻬王的中等⻢，勉强获胜。
由此，我们可以得出⼀个最优的决策⽅式：
a. 当⼰⽅此时最差的⽐不过对⾯最差的时候，让我⽅最差的去处理掉对⾯最好的（反正要输，不
如去拖掉对⾯⼀个最强的）；
b. 当⼰⽅此时
c. 最差的能⽐得上对⾯最差的时候，就让两者⽐对下去（最差的都能获胜，为什么要输呢）。每次决策，都会使我⽅处于优势。
编写代码
c++算法代码：
class Solution
{
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();// 1. 排序sort(nums1.begin(), nums1.end());vector<int> index2(n);for(int i = 0; i < n; i++) index2[i] = i;sort(index2.begin(), index2.end(), [&](int i, int j){return nums2[i] < nums2[j];});// 2. ⽥忌赛⻢vector<int> ret(n);int left = 0, right = n - 1;for(auto x : nums1){if(x > nums2[index2[left]]) ret[index2[left++]] = x;else ret[index2[right--]] = x;}return ret;}
};java">class Solution
{public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums1.length;// 1. 排序Arrays.sort(nums1);Integer[] index2 = new Integer[n];for(int i = 0; i < n; i++) index2[i] = i;Arrays.sort(index2, (i, j) -> {return nums2[i] - nums2[j];});// 2. ⽥忌赛⻢int[] ret = new int[n];int left = 0, right = n - 1;for(int x : nums1){if(x > nums2[index2[left]]){ret[index2[left++]] = x;}else{ret[index2[right--]] = x;}}return ret;}
}
