字符串的非重复字符

给定一个字符串* Str的ASCII字符，编写伪代码以删除其中存在的重复元素。例如，如果给定的字符串是“土豆”，那么输出必须是“Pota”。额外的限制是，该算法必须在原地。字符串的非重复字符

我写了一个程序，其中包含255个元素的bool数组，并保持它们的值为false。在遍历字符串时，我将它们的值更改为true以将它们标记为已访问并以这种方式获得另一个唯一值字符串。通过这种方式，我使用了恒定的空间。有没有更好的方法来做到这一点。

来源

2011-07-16 algo-geeks

您所使用的词语 “另一个字符串”，也许，只是也许，你有2个字符串？原地的想法是，你用同一个字符串来做。但是，也许你只是指“另一个字符串内容”，所以是的，那就没问题。为了说明：给出了字符串，并在其开始处指定了两个指针，然后使读取指针每次读取一个字符，只有在字符尚未处于写入中时才写入（并因此增加写入指针）你的255表。

来源

2011-07-16 13:36:13

您需要一个布尔值数组您的字母表大小为（例如，26为小写拉丁字母）。然后遍历字符串，并检查每个字母是否相应的数组字段为真。如果不是，请将其设置为true。然后删除这封信。要删除字母，请记下已经删除了多少字母，然后将每个字母复制到左侧。由于这听起来像是功课，所以我把这些伪代码的写法留给你。

来源

2011-07-16 13:34:08

为了使您的解决方案到位，而不是使用输出数组，只需将输入数组中的下一个字符左移到当前位置，无论何时要删除字符。

伪代码：

for each position in input_array: 
    c=input_array[position] 
    if we have already seen c 
     shift left all characters position+1 by one character. 
     position=position-1 // so that we process this character in the next iteration 
    else 
     mark c as seen 
    end if

来源

2011-07-16 13:34:24 MAK

该算法在第一次替换后会运行到无限循环。如果您将字符'i + 1'复制到'i'，然后再次查看'i'，您会发现您已经看到了该字符，因此您将'i + 1'复制到'i'并查看在'我'再次等... –

@ Space_C0wB0y：谢谢，更新了我的答案。 – MAK

但现在你已经使它成为一个n^2的解决方案，如果这是一个家庭作业问题，我不认为这将足够:) –

下面是一些伪代码：

seen is array of 256 boolean, initially all false 
output position is start of string 
for each position in string: 
    c is char at position 
    if seen[c] is false: 
     set seen[c] to true 
     set char at output position to c 
     increment output position

输出字符串在output position结束。不要忘记设置输出字符串的长度或者根据不同的编程语言添加它的终止符。

来源

2011-07-16 14:13:52 MRAB

字符串的非重复字符

回答

相关问题