从字符串中删除重复项,不使用HASHMAP和O(n)时间复杂度

Question

微软面试问题

从字符串中删除重复项,不使用HASHMAP和O(n)时间复杂度

O(n ²)时间复杂度有一个解决方案,但面试问题特别提到了没有HASHMAP和O(n)时间.

任何指针都很受欢迎,因为我不能想到任何低于O(n log n)时间的东西,它采用排序并使用O(n)空间.

Answer 1

你做了一种斗式排序.

我们使用这样的2个数组的唯一原因是因为你明确禁止哈希映射.您可以随意代表这种结构.如果允许将字符转换为ints,则只需使用1个数组.

由于我们假设可能的字符数量有限,每个数组将是常量大小,或者O(1)

在char数组中搜索特定的char会花费O(1)时间,因为字符数量有限.

您将对此次搜索进行n次搜索,以获得O(n)的净运行时间

如果数组不好,那么你可以创建一个链表来保存你找到的值.它仍然是常量,因为链表的大小仍然受可能字符数的限制.

如果你这样做,你或多或少会做同样的事情,除了它在外观上看起来不像桶式排序策略.

@Spandan O(1)空间并不意味着没有额外的空间. (6认同)
@ Spandan-这个答案满足你所有的约束 - 它在O(n)时间运行并使用O(1)空间.请记住,O(1)空间并不意味着"没有额外的存储空间".这意味着"最多使用一定量的辅助存储空间".由于字符串中只有可能的字符数,因此包含它们的哈希映射将仅使用O(1)辅助存储空间.常数可能很大,但它仍然是常数. (6认同)
@Spandan那不是HASHmap,因为它不使用散列. (5认同)
@Spandan,也许从技术上讲,数组可以被认为是散列映射的一个子集,其中散列是标识函数,并且不存在冲突的可能性.但大多数人并不这么认为,可能包括你的面试官.这真是一个巨大的差异. (4认同)