首页 > 剑指offer > 删除重复字符
2014
07-01

删除重复字符

Cracking the coding interview–Q1.3

原文:

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

FOLLOW UP

Write the test cases for this method.

译文:

设计算法并写出代码移除字符串中重复的字符,不能使用额外的缓存空间。注意: 可以使用额外的一个或两个变量,但不允许额外再开一个数组拷贝。

进一步地,

为你的程序写测试用例。

解答

这道题目其实是要你就地(in place)将字符串中重复字符移除。你可以向面试官问清楚, 不能使用额外的一份数组拷贝是指根本就不允许开一个数组,还是说可以开一个固定大小, 与问题规模(即字符串长度)无关的数组。

方法1

如果根本就不允许你再开一个数组,只能用额外的一到两个变量。那么,你可以依次访问 这个数组的每个元素,每访问一个,就将该元素到字符串结尾的元素中相同的元素去掉( 比如置为’\0′ 或 0).时间复杂度为O(n2 )

方法2

如果可以开一个固定大小,与问题规模(即字符串长度)无关的数组,那么可以用一个数组来 表征每个字符的出现(假设是ASCII字符,则数组大小为256),这样的话只需要遍历一遍字符 串即可,时间复杂度O(n)。

方法3

如果字符集更小一些,比如只是a-z,即字符串里只包含小写字母,那么使用一个int变量中 的每一位来表征每个字符的出现,一样可以在O(n)的时间里移除重复字符,而且还不需要额 外开一个数组。

测试用例

  1. 不包含重复字符的字符串,比如:abcd
  2. 字符串全是重复字符,比如:aaaa
  3. 空字符串
  4. 重复字符连续出现,比如:aaabbb
  5. 重复字符不连续出现,比如:abababa

完整C++代码如下:

//============================================================================
// Name        : 删除重复字符.cpp
// Author      : Coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

//方法1,复杂度n^2
void removeDuplicate(char s[]) {
	int len = strlen(s);
	int j = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] != 0) {
			s[j++] = s[i];
			for (int k = i + 1; k < len; k++) {
				if (s[k] == s[i]) {
					s[k] = 0;
				}
			}
		}
	}
	s[j] = 0;
}

//方法2,复杂度为n,假设所有字符在ASCII表范围内
void removeDuplicate2(char s[]) {
	bool h[256];
	memset(h, 0, sizeof(h));
	int i = 0;
	int j = 0;
	while (s[i]) {
		if (!h[(int) s[i]]) {
			s[j++] = s[i];
			h[(int) s[i]] = true;
		}
		i++;
	}
	s[j] = 0;
}

//方法3,复杂度为n,假设所有的字符都是 a-z 范围内
void removeDuplicate3(char s[]) {
	int h = 0;
	int i = 0;
	int j = 0;
	while (s[i]) {
		int bit = 1 << (int) (s[i] - 'a');
		if ((h & bit) == 0) {
			s[j++] = s[i];
			h |= bit;
		}
		i++;
	}
	s[j] = 0;
}

//测试
int main() {
	/*
	 测试用例:
	 不包含重复字符的字符串,比如:abcd
	 字符串全是重复字符,比如:aaaa
	 空字符串
	 重复字符连续出现,比如:aaabbb
	 重复字符不连续出现,比如:abababa
	 */

	char testStrs[5][100] = { "abadeaaa", "aaaaa", "abcde", "", "aaddddee" };
	for (int i = 0; i < 5; i++) {
		removeDuplicate(testStrs[i]);
		printf("%s\n", testStrs[i]);
	}
	puts("--------------------");
	for (int i = 0; i < 5; i++) {
		removeDuplicate2(testStrs[i]);
		printf("%s\n", testStrs[i]);
	}
	puts("--------------------");
	for (int i = 0; i < 5; i++) {
		removeDuplicate3(testStrs[i]);
		printf("%s\n", testStrs[i]);
	}
	puts("--------------------");
	return 0;
}

参考:作者:Hawstein   出处:http://hawstein.com/posts/1.3.html


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  4. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确