Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
例子：
1
2
|
String s = "foobarzyx"; // o重复
String s = "abefzpsln"; // unique
|
Bitmap
如果字符集是26个小写英文字母+26个大些英文字母+10个数字=62个字符，那么可以用bitmap，那可以用int/long作为一个bitmap来记录字母的出现情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public boolean isUnique(String s) {
if (s.length() <= 1) {
return true;
}
long bitmap = 0L;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
long bit = 1L << (c - 'a');
if (bitmap & bit != 0) {
return false;
}
bitmap |= bit;
}
return true;
}
|
时间复杂度：O(n)
空间复杂度：O(1)
先排序再遍历
如果字符集很大，比如说ASCII 256个字符，可以采用先排序再遍历的办法。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public boolean isUnique(String s) {
if (s.length() <= 1) {
return true;
}
char[] chars = s.charArray();
Arrays.sort(chars);
for(int i = 1; i < chars.length; i++) {
if (chars[i - 1] == chars[i]) {
return false;
}
}
return true;
}
|
时间复杂度：排序占用O(nlogn)，遍历O(n)，所以复杂度=O(nlogn)
空间复杂度：O(n)
用boolean数组
已知字符集范围（比如128个字符），可以用boolean数组来解决：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public boolean isUnique(String s) {
if (s.length() <= 1) {
return true;
}
if (s.length() > 128) {
// 肯定存在重复
return false;
}
boolean[] flags = new boolean[128];
for(int i = 0; i < s.length(); i++) {
int pos = s.charAt(i);
if (flags[pos]) {
return false;
}
flags[pos] = true;
}
return true;
}
|
时间复杂度：O(min(c, n))，c=字符集的大小，n=字符串长度，遍历的次数不会超过c
空间复杂度：O(c)，c=字符集的大小
评论