字符串去重,用C有比线性时间复杂度更低的算法吗?

newbee617
newbee617 2014-12-12 字数 228

比如“abcba”去重后变为"abc"。

我能想到的是使用hash表,首先把hash表中的值全部置为0,然后遍历一边字符串,查询当前字符在hash表中对应位置的值,如果为0则输出,同时把hash表对应位置的值置为1;如果为1则查询下一个字符。

时间复杂度为O(n)。

Algorithm 算法
8 个回复
milksea
肥了,又肥了 >>>_<<< 2014-12-12

每个字符总得都读一遍吧?若不需要读某字符,则不可能知道它是否与其他字符重复。

于是最少线性时间。

【 在 newbee617 () 的大作中提到: 】

: 比如“abcba”去重后变为"abc"。

: 我能想到的是使用hash表,首先把hash表中的值全部置为0,然后遍历一边字符串,查询当前字符在hash表中对应位置的值,如果为0则输出,同时把hash表对应位置的值置为1;如果为1则查询下一个字符。

: 时间复杂度为O(n)。

: ...................

qblyy
新的昵称 2014-12-12

这不是常考的面试题么

如果是ascii字符的话,bitmap更快

宽字符的话,hashset可能更快

【 在 newbee617 () 的大作中提到: 】

: 比如“abcba”去重后变为"abc"。

: 我能想到的是使用hash表,首先把hash表中的值全部置为0,然后遍历一边字符串,查询当前字符在hash表中对应位置的值,如果为0则输出,同时把hash表对应位置的值置为1;如果为1则查询下一个字符。

: 时间复杂度为O(n)。

: ...................

newbee617
newbee617 2014-12-12

你是说的java吗,java中没有bitmap吧?

【 在 qblyy 的大作中提到: 】

: 这不是常考的面试题么

: 如果是ascii字符的话,bitmap更快

: 宽字符的话,hashset可能更快

: ...................

qblyy
新的昵称 2014-12-12

C++ Java都有

速度其实慢,但占的内存少

char/byte数组也可以

【 在 newbee617 () 的大作中提到: 】

: 你是说的java吗,java中没有bitmap吧?

newbee617
newbee617 2014-12-12

java中没有bitmap啊。

另外java中array应该比任何容器都快吧。

【 在 qblyy 的大作中提到: 】

: C++ Java都有

: 速度其实慢,但占的内存少

: char/byte数组也可以

: ...................

Fermat
Fermat 2014-12-12

Bitmap 是每一个 bit 表示一个状态?这样速度不如 char [256] 吧,毕竟计算机是以字节为单位进行处理的,访问单独的位要通过位操作。不是成千上万个的话,32 个字节与 256 个字节的内存大小区别可以忽略。

【 在 qblyy (找美国程序员工作) 的大作中提到: 】

: C++ Java都有

: 速度其实慢,但占的内存少

: char/byte数组也可以

newbee617
newbee617 2014-12-25

哦,你说的是bitset吧?比数组慢但是省空间的java1.1中的容器?

【 在 qblyy 的大作中提到: 】

: C++ Java都有

: 速度其实慢,但占的内存少

: char/byte数组也可以

: ...................

eastseek
eastseek 2014-12-31

不太可能比线性时间更短了吧。就是做倒排你也得先线性遍历再倒排啊。