string - 使用另一个排序顺序字符串对字符串进行排序

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

5年前关闭。




Improve this question




我在面试问题中看到了这个，
给定一个排序顺序字符串，您需要根据给定的排序顺序字符串对输入字符串进行排序。
例如，如果排序字符串是 dfbcae 并且输入字符串是 abcdeeabc 输出应该是 dbbccaaee .

关于如何以有效的方式做到这一点的任何想法？

Answer 1

Counting Sort选项非常酷，并且当要排序的字符串与排序顺序字符串相比很长时速度很快。

创建一个数组，其中每个索引对应字母表中的一个字母，这就是计数数组

对于排序目标中的每个字母，递增计数数组中与该字母对应的索引

对于排序顺序字符串中的每个字母

将该字母添加到输出字符串末尾的次数等于它在计数数组中的计数

算法复杂度为 O(n)哪里 n是要排序的字符串的长度。正如维基百科文章所解释的，我们能够超越基于标准比较的排序的下限，因为这不是基于比较的排序。

这是一些伪代码。

char[26] countArray;
foreach(char c in sortTarget)
{
    countArray[c - 'a']++;
}

int head = 0;
foreach(char c in sortOrder)
{
    while(countArray[c - 'a'] > 0)
    {
        sortTarget[head] = c;
        head++;
        countArray[c - 'a']--;
    }
}

注意:这个实现要求两个字符串都只包含小写字符。