[字符串原地压缩][代码实现]

题目

字符串原地压缩。题目描述：“eeeeeaaaff" 压缩为 "e5a3f2"，请编程实现。

 

思想

 

首先想到最简单的方法是创建一个数组，一次遍历就可以将原字符串压缩。时间复杂度O(N)，空间复杂度O（N）。但这种方法不符合题意，题目要求原地压缩。那么空间复杂度应该是O（1）。

 

如果使用原地压缩，最麻烦的就是移动数据。如果不用移动数据，就能达到时间复杂度O（N），空间复杂度为O（1）。

 

不移动数据，可以增加一个标记。标记压缩后的字符串的长度。这样就可以一个数组两个用途了。

 

问题

如下的字符串“abcccc”，压缩后a1b1c4。另外字符串“abc”压缩后成了“a1b1c1”。这两种情况下，上述方法就不好用了。尤其第二种情况下，压缩后的数组比压缩前还长。 对于这两种情况，因为题目没有规定长度为1的情况的处理情况，不如咱们假设如果长度为1的字符，后面不用1。这样就简化了问题。

 

另外，还有一个问题，就是在其中一个字符长度大于9时的处理方法。如果长度大于9，需要获取到长度位数，然后将长度数字copy到String上。下面实现的代码没有考虑这种情况。

 

 

代码

 

/**
 * 原地压缩
 * 字符串原地压缩。题目描述：“eeeeeaaaff" 压缩为 "e5a3f2"，请编程实现。
 * @author ajwang
 *
 */
public class PlaceCompress {
	
	public static void main(String[] args) {
		char[] string = "aabbccddeeffg".toCharArray();
		int end = placeCompress(string);
		System.out.println(String.copyValueOf(string,0,end+1));
	}
	public  static int placeCompress(char[] string) {
		int length = string .length;
		int compressLength = 0;
		int count = 1;
		for(int i=1;i<length;i++) {
			if(string[i]==string[compressLength]) {
				count++;
			} else {
				if(count!=1) {
					compressLength++;
					string[compressLength]=(char) ('0'+count%10);
					
				} 
				compressLength++;
				string[compressLength]= string[i];
				count = 1;
			}
			//当处理结束时，需要计算一下最后一个字符出现的次数
			if(i==length-1) {
				if(count!=1) {
					compressLength++;
					string[compressLength]=(char) ('0'+count);
				}
				
			}
			
			
		}
		return compressLength;
	}
}