目录
按⾝⾼排序（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;
}
}