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

Question

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

有没有什么高效的方法可以解决这个问题？

- Mouna Cheikhna

Answer 1

计数排序 选项非常酷，当要排序的字符串较长时，速度很快。

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

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

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

- Waylon Flinn

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++;
        }
    }
}

- Waylon Flinn

Answer 3

在C#中，我会使用IComparer接口，并将其留给Array.Sort处理。

void Main()
{
   // we defin the IComparer class to define Sort Order
   var sortOrder = new SortOrder("dfbcae");

   var testOrder = "abcdeeabc".ToCharArray();
   // sort the array using Array.Sort
   Array.Sort(testOrder, sortOrder);

   Console.WriteLine(testOrder.ToString());

}
public class SortOrder : IComparer
{
   string sortOrder;

  public SortOrder(string sortOrder)
  {
    this.sortOrder = sortOrder; 
  }

public int Compare(object obj1, object obj2)
{
    var obj1Index = sortOrder.IndexOf((char)obj1);
    var obj2Index = sortOrder.IndexOf((char)obj2);

    if(obj1Index == -1 || obj2Index == -1)
    {
        throw new Exception("character not found");
    }

    if(obj1Index > obj2Index)
    {
        return 1;
    }
    else if (obj1Index == obj2Index)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}

}

- Solanki

Answer 4

在Python中，您只需创建一个索引并在比较表达式中使用它：

order = 'dfbcae'
input = 'abcdeeabc'

index = dict([ (y,x) for (x,y) in enumerate(order) ])
output = sorted(input, cmp=lambda x,y: index[x] - index[y])

print 'input=',''.join(input)
print 'output=',''.join(output)

会输出以下内容：

input= abcdeeabc
output= dbbccaaee

- eduffy

Answer 5

面试问题通常涉及思维过程，不太关心语言特性，但我还是忍不住要发布一个VB.Net 4.0版本。

"高效"可以有两种不同的含义。第一种是“让计算机执行任务的最快方式”，第二种是“我们能够完成任务的最快方式”。它们听起来可能相同，但第一种可以意味着微观优化，比如int vs short，运行计时器以比较执行时间，并花费一周的时间将算法中的每个毫秒调整到极致。第二个定义是关于创建执行任务的代码需要多少人类时间（希望在合理的时间内完成）。如果代码A比代码B运行速度快20倍，但编写代码B只用了1/20的时间，根据计时器的粒度（1ms vs 20ms，1周vs 20周），每个版本都可以被认为是“高效”的。

    Dim input = "abcdeeabc"
    Dim sort = "dfbcae"

    Dim SortChars = sort.ToList()
    Dim output = New String((From c In input.ToList() Select c Order By SortChars.IndexOf(c)).ToArray())
    Trace.WriteLine(output)

- Chris Haas

Answer 6

这是我的版本，时间复杂度为 O(n)。我可以使用大小固定的 char 数组来替代 unordered_map，例如：char char_count[256]，然后做 ++char_count[ch - 'a']，前提是输入的字符串都是 ASCII 小写字母。

string SortOrder(const string& input, const string& sort_order) {
  unordered_map<char, int> char_count;
  for (auto ch : input) {
    ++char_count[ch];
  }
  string res = "";
  for (auto ch : sort_order) {
    unordered_map<char, int>::iterator it = char_count.find(ch);
    if (it != char_count.end()) {
      string s(it->second, it->first);
      res += s;
    }
  }
  return res;
}

- Bikash

---

这是我自己的版本，时间复杂度为O(n)。与其使用unordered_map，我可以使用一个定长的char数组。例如：char char_count[256]（然后用++char_count[ch - 'a']来表示）假设输入字符串只包含ASCII小写字母。 - Bikash

你可以编辑你的回答。你发布的评论应该包含在你的回答中。我已经为你完成了这个任务，但你应该记住下次要这样做。 - Artjom B.

Answer 7

    private static String sort(String target, String reference) {
    final Map<Character, Integer> referencesMap = new HashMap<Character, Integer>();

    for (int i = 0; i < reference.length(); i++) {
        char key = reference.charAt(i);
        if (!referencesMap.containsKey(key)) {
            referencesMap.put(key, i);
        }
    }

    List<Character> chars = new ArrayList<Character>(target.length());
    for (int i = 0; i < target.length(); i++) {
        chars.add(target.charAt(i));
    }

    Collections.sort(chars, new Comparator<Character>() {
        @Override
        public int compare(Character o1, Character o2) {
            return referencesMap.get(o1).compareTo(referencesMap.get(o2));
        }
    });

    StringBuilder sb = new StringBuilder();
    for (Character c : chars) {
        sb.append(c);
    }

    return sb.toString();
}

- Omar Salem

Answer 8

这是我的问题解答方案。

import java.util.*;
import java.io.*;

class SortString
{
public static void main(String arg[])throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    // System.out.println("Enter 1st String :");
    // System.out.println("Enter 1st String :");
    // String s1=br.readLine();
    // System.out.println("Enter 2nd String :");
    // String s2=br.readLine();
    String s1="tracctor";
    String s2="car";
    String com="";
    String uncom="";
    for(int i=0;i<s2.length();i++)
    {
        if(s1.contains(""+s2.charAt(i)))
        {
                com=com+s2.charAt(i);

        }
    }
    System.out.println("Com :"+com);
    for(int i=0;i<s1.length();i++)
        if(!com.contains(""+s1.charAt(i)))
        uncom=uncom+s1.charAt(i);

    System.out.println("Uncom "+uncom);
    System.out.println("Combined "+(com+uncom));
    HashMap<String,Integer> h1=new HashMap<String,Integer>();

    for(int i=0;i<s1.length();i++)
    {
        String m=""+s1.charAt(i);

        if(h1.containsKey(m))
        {
            int val=(int)h1.get(m);
            val=val+1;
            h1.put(m,val);
        }
        else
        {
            h1.put(m,new Integer(1));

        }
    }
    StringBuilder x=new StringBuilder();
    for(int i=0;i<com.length();i++)
    {
        if(h1.containsKey(""+com.charAt(i)))
        {
            int count=(int)h1.get(""+com.charAt(i));
            while(count!=0)
            {x.append(""+com.charAt(i));count--;}
        }
    }
    x.append(uncom);
    System.out.println("Sort "+x);

}

}

- Akshay

Answer 9

使用二分查找来查找不同字母之间的所有“分割点”，然后直接使用每个段的长度。这将比朴素的计数排序渐进地更快，但实现起来会更困难：

• 使用大小为26*2的数组来存储每个字母的开始和结束位置；

• 检查中间元素，看它是否与左边的元素不同。如果是，则这是中间元素的开始位置和前一个元素的结束位置；

• 丢弃具有相同开始和结束位置的段（如果有），递归应用此算法。

由于最多有25个“分割点”，因此您不必搜索超过25个段，对于每个段，它的时间复杂度为O(logn)。由于这是常数 * O(logn)，所以该算法的时间复杂度为O(nlogn)。

当然，只需使用计数排序就更容易实现：

• 使用大小为26的数组记录不同字母的数量；

• 扫描输入字符串；

• 按给定的排序顺序输出字符串。

这是O(n)的时间复杂度，其中n是字符串的长度。

- zw324