首页 > 代码库 > 美团2015校招哈尔滨站笔试题--第二题
美团2015校招哈尔滨站笔试题--第二题
有一组随机排列的字母数组，请编写一个时间复杂度为O(n)的算法，使得这些字母安装字母从小到大顺序排好。
说明：字母区分大小写，相同的字母，排序后小写排在大写前。
例如：R,B,B,b,W,W,B,R,B,w
排序后：b,B,B,B,B,R,R,w,W,W
1)描写思路（2分）
2）请用你熟悉的编程语言编写代码实现（8分）
/** * * @author 无心流泪 * 空间换时间 */public class InterviewExercise { public void mySort(char[] str){ int[] hash = new int[52]; for(int i=0;i<str.length;i++){ if(str[i]>=97) { int key = str[i] - 97; hash[key*2]++; }else{ int key = str[i] - 65; hash[key*2+1]++; } } int count = 0; for(int i=0;i<52;i++){ while(hash[i]!=0){ if(i%2==0){ str[count]= (char)(i+97-i/2); }else{ str[count]= (char)(i+65-i/2-1); } hash[i]--; count++; } } } public static void main(String[] args) { char[] characterArray = {‘R‘,‘B‘,‘B‘,‘b‘,‘W‘,‘W‘,‘B‘,‘R‘,‘B‘,‘w‘}; new InterviewExercise().mySort(characterArray); for(int i=0;i<characterArray.length;i++) System.out.print(characterArray[i]+" "); }}
思路很简单，开一个52的int数组，顺序代表a，A，b，B，c，C，d..........z,Z这些字母出现的次数；然后再依次打印出数组中保存的字母就可以了，采取空间换时间的hash策略。
下面的代码是字符比较的另一种方式，感觉更好点，来自http://www.dy1280.com/thread-440-1-1.html
public static void main(String[] args) { // A=65,Z=90 a=97,z=122 char[] src = http://www.mamicode.com/{ ‘R‘, ‘B‘, ‘B‘, ‘b‘, ‘W‘, ‘W‘, ‘B‘, ‘R‘, ‘B‘, ‘w‘ }; src = sortCharsOn(src); for (char c : src) { System.out.print(c + " "); } } /** * O(n)的时间复杂度对给定的字符数组进行排序 * * @param src * 原数组 * @return 排序后的数组 */ private static char[] sortCharsOn(char[] src) { int[] items = new int[54];// 用于保存52个字符 char[] des = new char[src.length]; for (int i = 0; i < src.length; i++) { if (src[i] < ‘z‘ && src[i] > ‘a‘) { // 小写对应于items中下标为偶数 items[(src[i] - ‘a‘) * 2]++; } else if (src[i] < ‘Z‘ && src[i] > ‘A‘) { // 大写对应于items中下标为奇数 items[(src[i] - ‘A‘) * 2 + 1]++; } } int index = 0; for (int i = 0; i < items.length; i++) { if (items[i] != 0) {// items[i],就是该字符出现的次数 if (i % 2 == 0) { for (int j = 0; j < items[i]; j++) { des[index++] = (char) (i / 2 + ‘a‘);// 转化成小写 } } else { for (int j = 0; j < items[i]; j++) { des[index++] = (char) ((i - 1) / 2 + ‘A‘);// 转化成大写 } } } } return des; }
美团2015校招哈尔滨站笔试题--第二题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。