By

文章目录

创新工场面试题目

一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后，而且各部分内部分别有序。

此题网上看到别人的做法都说的比较迷糊，好多也都是用快排之类来做的，现在来说一下我的思路：可以将这些字符转为ascii码，小写在前，大小在中间，数字在最后，正好是按ascii倒着排过来，现在已经确认待排序的内容都是在ascii的范围内，所以可以借鉴位排序的方法，申请一个128位的int数组，将每个字符映射到这个数组里面，多个出现在字符累加起来，如果没有出现则置0，最后按顺序输出即可，不需要任何比较。最终整个算法的复杂度为O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
char[] cs={'a','Q','7','b','9','P','a','c','8','O','Q','d','N','2','e','M'};
int[] ascii=new int[128];


for(int i=0;i<cs.length;i++)
{
	ascii[cs[i]]+=1;//逐个对应的放入桶中
}

int t=0;
for(int i=97;i<=122;i++)//输出小写字母到cs原数组中
{
	for(int j=0;j<ascii[i];j++)
	{
		cs[t++]=(char)i;
	}
}

for(int i=65;i<=90;i++)//输出大小字母
{
	for(int j=0;j<ascii[i];j++)
	{
		cs[t++]=(char)i;
	}
}

for(int i=48;i<=57;i++)//输出数字
{
	for(int j=0;j<ascii[i];j++)
	{
		cs[t++]=(char)i;
	}
}

for(int i=0;i<cs.length;i++)
{
	System.out.print(cs[i]);//最后正真输出
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录