【题目】
给定一个字符类型的数组chas,请在单词间做逆序调整。只要做到单词顺序逆序即可,对空格的位置没有特别要求
举例,如果把chas看作字符串为"dog loves pig",调整成"pig loves dog";如果把chas看作字符串为"I'm a student.",调整成"student. a I'm"
【要求】
如果chas长度为N,要求时间复杂度为O(N),空间复杂度为O(1)
【分析】
首先将整个单词序列逆序,逆序后再将每个单词逆序,即可将单词顺序逆序。如"dog loves pig",首先将整个单词序列逆序得到"gip sevol god",然后将每个单词逆序,得到"pig loves dog"。整个过程都实在元字符数组的基础上完成的,所以空间复杂的为O(1),全程总共只遍历了整个字符数组两次,所以时间复杂度为O(N)
1 public void rotateWord(char[] chas) 2 { 3 if(chas == null || chas.length == 0) 4 { 5 return; 6 } 7 8 reverse(chas, 0, chas.length -1); // 先将整个单词序列逆序 9 int left = -1; // left跟踪单词的左边界 10 int right = -1; // right跟踪单词的右边界 11 for(int i = 0; i < chas.length; i++) 12 { 13 if(chas[i] != ' ') 14 { 15 left = i == 0 || chas[i-1] == ' ' ? i : left; 16 right = i == chas.length || chas[i+1] == ' ' ? i : right; 17 } 18 if(left != -1 && right != -1) 19 { 20 reverse(chas, left, right); // 然后将单个单词逆序 21 left = -1; 22 right = -1; 23 } 24 25 } 26 } 27 28 29 public void reverse(char[] chas, int start, int end) 30 { 31 char temp; 32 33 while(start < end) 34 { 35 temp = chas[start]; 36 chas[start] = chas[end]; 37 chas[end] = temp; 38 start++; 39 end--; 40 } 41 } 42 43
来源:左程云老师《程序员代码面试指南》