以下为ChatGPT自动生成的解答,正确与否请自行判断。 也许你也可以从大家的发帖中找到想要的答案!
BFE.devAI解答 - JavaScript 代码题
105. 找到第一个重复的字符
一种解法是使用一个对象来记录每个字符出现的次数,并遍历字符串,查找第一个出现次数大于1的字符即可。
代码如下:
function firstDuplicate(str) { const charCount = {}; for (let i = 0; i < str.length; i++) { const char = str[i]; if (charCount[char]) { return char; } else { charCount[char] = 1; } } return null;}
时间复杂度为O(n),空间复杂度也为O(n),因为需要使用一个对象来存储每个字符出现的次数。
如果不想使用额外的空间,可以考虑使用双重循环,但是时间复杂度会变为O(n^2)。
改善的办法是使用一个Set数据结构,记录已经出现过的字符,遍历字符串时,如果发现当前字符已经在Set中出现过,则找到了第一个重复的字符。
代码如下:
function firstDuplicate(str) { const charSet = new Set(); for (let i = 0; i < str.length; i++) { const char = str[i]; if (charSet.has(char)) { return char; } else { charSet.add(char); } } return null;}
时间复杂度为O(n),空间复杂度也为O(n),但是相比于第一种解法,使用Set数据结构能够更快地查找重复字符,因此可能更优秀一些。