为什么该算法检查一个数组是否全部具有唯一字符O(n)？
提问于 2020-07-05 15:42:00
在“破解编码面试”一书中，第一个练习说“实现一个算法来确定一个字符串是否都具有唯一的字符(不使用额外的数据结构)”。解决方案是：
public static boolean isUniqueChars(String str) {
boolean [] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}然后他们说“时间复杂度是O(n)，其中n是字符串的长度，空间复杂度是O(n)”。
我不明白为什么空间复杂度是O(n)。数组char_set的长度是恒定的，与给定的str的长度无关。对我来说，空间复杂度是O(1)。
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-07-05 15:59:53
它的空间复杂度是O(1) (\Theta(1))，因为它保持比输入数组大小多256 (常量)位。而且，时间复杂度是O(1)的，因为在输入字符串中有256个字符要检查，并且最多将检测到字符串的第256个字符的重复。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62742879
复制相关文章
腾讯云开发者
