string - 在 O(n) 时间内用常量空间(即没有额外的辅助数组)在给定字符串中查找非唯一字符

Question

给定一个仅包含小写字母 (a - z) 的字符串 s，找出(即打印)重复的字符。

例如，如果字符串 s = "aabcacdddec"

输出:a c d

存在 3 种解决此问题的方法:

1. [brute force] 检查字符串的每个字符(即 s[i] 与其他每个字符，如果两者相同则打印)时间复杂度:O(n^2)空间复杂度:O(1)

2. [排序然后比较相邻元素]排序后(O(n log(n)时间)遍历字符串，检查s[i] ans s[i + 1]是否相等时间复杂度:O(n logn) + O(n) = O(n logn)空间复杂度:O(1)

3. [将字符数存储在一个数组中] 创建一个大小为 26 的数组(以跟踪 a - z)并为每个 s[i]，增加存储在索引 = s[i] - 26 的值在数组中。最后遍历数组并打印所有值大于1的元素(即'a'+ i)时间复杂度:O(n)空间复杂度:O(1) 但我们有一个单独的数组来存储每个元素的频率。

有没有不使用任何数组/哈希表/映射(等)的 O(n) 方法？

提示:使用位向量

Answer 1

这是 element distinctness problem ，所以一般来说 - 不，没有额外的空间，没有办法在 O(n) 中解决它。

但是，如果您将字母表视为恒定大小(只有 a-z 字符非常恒定)，您可以创建这些字符的位集，O(1)空格 [它是常量!] 或者检查 O(n) 中的每个字符，如果它重复多次，它将是 O(constant*n)，这是仍在 O(n) 中。

第一个解决方案的伪代码:

bit seen[] = new bit[SIZE_OF_ALPHABET] //contant!
bit printed[] =  new bit[SIZE_OF_ALPHABET] //so is this!
for each i in seen.length: //init:
    seen[i] = 0
    printed[i] = 0
for each character c in string: //traverse the string:
    i = intValue(c)
    //already seen it and didn't print it? print it now!
    if seen[i] == 1 and printed[i] == 0: 
        print c
        printed[i] = 1
    else:
        seen[i] = 1

第二个解决方案的伪代码:

for each character c from a-z: //constant number of repeats is O(1)
   count = 0
   for each character x in the string: //O(n)
        if x==c:
           count += 1
   if count > 1
        print count