有一組隨機排列的字母數組，請編寫一個時間復雜度為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/2+97);}else{str[count]= (char)((i-1)/2+65);}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=122char[] src = { '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;}

?

轉載于:https://www.cnblogs.com/wuxinliulei/p/3979990.html

總結

以上是生活随笔為你收集整理的美团2015校招哈尔滨站笔试题--第二题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。