C++自定义字符串排序

假设我们有两个字符串S和T，它们都由小写字母组成。在S中，每个字母最多出现一次。S之前按某种自定义顺序排序过。我们需要对T的字符进行排列，使其与S排序的顺序匹配。更具体地说，如果x在S中出现在y之前，那么x将在返回的字符串中出现在y之前。

例如，如果S = “cba”而T = “abcd”，则输出将是“cbad”。因为“a”、“b”、“c”出现在S中，所以“a”、“b”、“c”的顺序应该是“c”、“b”和“a”。由于“d”没有出现在S中，它可以在T中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。

为了解决这个问题，我们将遵循以下步骤：

  • 将ret设置为空字符串

  • 定义一个map m，并将T中每个字符的频率存储到m中

  • 对于i从0到S的长度减1

    • x := S[i]

    • 对于j从0到m[x]减1

      • ret := ret + x

    • m[x] := 0

  • 对于m中的每个键值对it：

    • 如果it的值 > 0，则

      • 对于i从0到it的值减1

        • ret := ret连接it的键

  • 返回ret

示例(C++)

让我们来看下面的实现，以便更好地理解：

在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string customSortString(string S, string T) {
      string ret = "";
      unordered_map <char, int> m;
      for(int i = 0; i < T.size(); i++){
         m[T[i]]++;
      }
      for(int i = 0; i < S.size(); i++){
         char x = S[i];
         for(int j = 0; j < m[x]; j++){
            ret += x;
         }
         m[x] = 0;
      }
      unordered_map <char, int> :: iterator it = m.begin();
      while(it != m.end()){
         if(it->second > 0){
            for(int i = 0; i < it->second; i++)ret += it->first;
         }
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.customSortString("cba", "abcd"));
}

输入

"cba"
"abcd"

输出

cbad

更新于：2020年5月2日

438 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告