使用另一个排序顺序字符串对字符串排序

Question

我在面试问题中看到了这一点,给定一个排序顺序字符串,系统会要求您根据给定的排序顺序字符串对输入字符串进行排序.
例如,如果排序顺序字符串是 dfbcae ,输入字符串是abcdeeabc 输出应该是 dbbccaaee.

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

Answer 1

该计数排序时要排序的字符串长度相比排序顺序串的选择是非常酷,和快速.

• 创建一个数组,其中每个索引对应于字母表中的一个字母,这是count数组
• 对于排序目标中的每个字母,递增计数数组中与该字母对应的索引
• 对于排序顺序字符串中的每个字母
  • 将该字母添加到输出字符串的末尾,其次数等于count数组中的计数

算法复杂度是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']--;
    }
}

注意:此实现要求两个字符串仅包含小写字符.

Answer 2

这是一个很好的易于理解的算法，具有相当的算法复杂性。

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

• 扫描要排序的字符串，从第一个无序字符开始（您可以使用索引或指针跟踪该字符）
  • 当找到指定字符时，将其与第一个无序字符交换
  • 增加第一个无序字符的索引

这是O(n*m)，其中n是要排序的字符串的长度，m是排序顺序字符串的长度。我们能够突破基于比较的排序的下限，因为该算法并不真正使用比较。与计数排序一样，它依赖于您有一个预定义的有限外部排序集这一事实。

这是一些伪代码：

int head = 0;
foreach(char c in sortOrder)
{
    for(int i = head; i < sortTarget.length; i++)
    {
        if(sortTarget[i] == c)
        {
             // swap i with head
             char temp = sortTarget[head];
             sortTarget[head] = sortTarget[i];
             sortTarget[i] = temp;

             head++;
        }
    }
}