我在一道面试题中看到了这个问题,给定一个排序顺序字符串,要求根据给定的排序顺序字符串对输入字符串进行排序。
例如,如果排序顺序字符串是 dfbcae
,输入字符串是 abcdeeabc
,则输出应该是 dbbccaaee
。
有没有什么高效的方法可以解决这个问题?
计数排序 选项非常酷,当要排序的字符串较长时,速度很快。
算法复杂度为 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']--;
}
}
这是一个易于理解的算法,具有良好的算法复杂度。
对于排序顺序字符串中的每个字符:
这是 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++;
}
}
}
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;
}
}
}
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
面试问题通常涉及思维过程,不太关心语言特性,但我还是忍不住要发布一个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)
这是我的版本,时间复杂度为 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;
}
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();
}
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);
}
}
使用二分查找来查找不同字母之间的所有“分割点”,然后直接使用每个段的长度。这将比朴素的计数排序渐进地更快,但实现起来会更困难:
使用大小为26*2的数组来存储每个字母的开始和结束位置;
检查中间元素,看它是否与左边的元素不同。如果是,则这是中间元素的开始位置和前一个元素的结束位置;
丢弃具有相同开始和结束位置的段(如果有),递归应用此算法。
由于最多有25个“分割点”,因此您不必搜索超过25个段,对于每个段,它的时间复杂度为O(logn)。由于这是常数 * O(logn)
,所以该算法的时间复杂度为O(nlogn)。
当然,只需使用计数排序就更容易实现:
使用大小为26的数组记录不同字母的数量;
扫描输入字符串;
按给定的排序顺序输出字符串。
这是O(n)的时间复杂度,其中n是字符串的长度。