题目:

给定一个字符串str,判断字符串中是否所有字符都只出现过一次。
例如:
str: “abc”
返回true

str: “1231″
返回false

如果字符串的长度为N,分别根据两种要求实现这个功能:
第一种实现:时间复杂度O(N)
第二种实现:额外空间复杂度O(1),并有尽可能低的时间复杂度

 

解答:

第一种实现难度:士
第二种实现难度:尉
第一种实现非常简单,字符集是用范围的,这里假设其范围是[0,255],所以用一个长度为256的数组,在从左到右遍历字符串的过程中查询并记录每一种字符是否出现过,即可完成功能。具体请参看如下代码中的isUniqueLessTime方法。

 第二种实现是把字符串中所有字符排序,这样一来字符串中相同的字符便会靠在一起。然后再顺序遍历一遍就可以知道是否有相同字符靠在一起的情况。例如:”1231″,排序后为”1123″,顺序遍历时就可以发现”11″靠在了一起。
接下来我们该选择何种排序方式呢?O(N)的排序算法都不符合额外空间复杂度O(1)的要求。O(N*logN)的排序有并归排序、快速排序和堆排序等,其中只有堆排序理论上的额外空间复杂度是O(1),于是应该将目光锁定在堆排序上。
这里大家要注意一点,虽然堆排序理论上的额外空间复杂度为O(1),但堆排序常见的实现却使用了递归函数。用递归实现能做到额外空间复杂度为O(1)么?不能。
因为递归函数的调用与返回是基于函数栈实现的。就堆排来说,函数栈的空间复杂度为O(logN),所以第二种方法最核心的部分就变成了如何把堆排序用非递归的方式实现。

PS:希尔排序也是符合条件的,平均的时间复杂度为O(N*logN),额外空间复杂度O(1)。

本文提供了堆排序的非递归实现,因为堆排序为十分基础的排序算法,所以这里就不再详述,具体请参看如下代码中的heapSort方法;第二种实现的全部过程就是如下代码中的isUniqueLessSpace方法。

 

1 条评论

欢迎留言