gpt-3.5-turbo-0301· openai
Suzhen/CodeChat
给你一个字符串数组 str 和一个整数k,请你返回st 中第k个独一无二的字符串。如果少于k个独一无二的字符串,那么返回空字符串?列出几种算法解决,用js实现
- User
给你一个字符串数组 str 和一个整数k,请你返回st 中第k个独一无二的字符串。如果少于k个独一无二的字符串,那么返回空字符串?列出几种算法解决,用js实现
- Assistant
一种基本的算法思路是使用哈希表记录每个字符串出现的次数,然后再遍历一遍数组,找出出现次数为1的第k个字符串。
具体实现代码如下:
function findKthUniqueString(str, k) { const count = new Map(); for (const s of str) { count.set(s, (count.get(s) || 0) + 1); } let uniqueCount = 0; for (const s of str) { if (count.get(s) === 1) { uniqueCount++; if (uniqueCount === k) { return s; } } } return ''; }另外一种算法思路是使用桶排序,遍历一遍数组,统计每个字符串出现的次数,然后再使用桶排序对出现次数进行排序,最后从小到大遍历已排序的出现次数,找到第k个出现次数为1的字符串。
具体实现代码如下:
function findKthUniqueString(str, k) { const count = new Map(); for (const s of str) { count.set(s, (count.get(s) || 0) + 1); } const bucket = []; for (const [s, c] of count) { if (!bucket[c]) { bucket[c] = []; } bucket[c].push(s); } let uniqueCount = 0; for (const b of bucket) { if (b) { for (const s of b) { uniqueCount++; if (uniqueCount === k) { return s; } } } } return ''; }以上两种算法的时间复杂度都为O(n),其中n为字符串数组str的长度。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.