题目描述给你一个字符串数组namesnamesnames和一个由互不相同的正整数组成的数组heightsheightsheights。两个数组的长度均为nnn。对于每个下标iiinames[i]names[i]names[i]和heights[i]heights[i]heights[i]表示第 i 个人的名字和身高。请按身高 降序 顺序返回对应的名字数组namesnamesnames。示例 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。解法 1在这里不能直接对身高数组排序因为对身高数组排序后通过身高就找不到对应的名字了。所以我们先创建一个存放二元组的数组二元组是身高名字然后遍历身高数组将身高和对应的名字存到数组中最后按照身高对这个数组排序遍历这个数组按顺序取出所有的名字即可。这种做法在数组中存储了身高和名字两种信息比较耗费空间classSolution{usingPISpairint,string;public:vectorstringsortPeople(vectorstringnames,vectorintheights){vectorPISperson;for(inti0;iheights.size();i){person.push_back({heights[i],names[i]});}sort(person.begin(),person.end(),[](constPISp1,constPISp2){returnp1.firstp2.first;});vectorstringret;for(auto[height,name]:person){ret.push_back(name);}returnret;}};解法 2创建一个哈希表保存身高和名字的映射关系。先遍历身高数组将身高和名字的映射关系记录到哈希表里然后对身高数组排序再遍历身高数组从哈希表里提取出对应的名字即可。这种方法的缺陷是哈希表不能存重复的值如果存在两个人他们都的身高相同就找不到另外一个人的身高了此时哈希表的valvalval要保存一个字符串数组比较耗空间classSolution{vectorstringsortPeople(vectorstringnames,vectorintheights){unordered_mapint,stringhash;for(inti0;iheights.size();i){hash[heights[i]]names[i];}sort(heights.begin(),heights.end(),greaterint());vectorstringret;for(intheight:heights){ret.push_back(hash[height]);}returnret;}};解法 3对数组排序但是又不希望影响原来的映射关系的场景我们可以选择创建一个下标数组解决具体的步骤是创建一个下标数组按照题目要求对下标数组排序通过排完序的下标数组提取出原数组的信息以示例111为例下标数组刚开始保存了所有人的下标classSolution{vectorstringsortPeople(vectorstringnames,vectorintheights){vectorintindices(heights.size());for(inti0;iheights.size();i){indices[i]i;}sort(indices.begin(),indices.end(),[](inti,intj){returnheights[i]heights[j];});vectorstringret;for(inti:indices){ret.push_back(names[i]);}returnret;}};
