Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· openaiHugging Face Suzhen/CodeChat

给你一个字符串数组 str 和一个整数k,请你返回st 中第k个独一无二的字符串。如果少于k个独一无二的字符串,那么返回空字符串?列出几种算法解决,用js实现

  1. User

    给你一个字符串数组 str 和一个整数k,请你返回st 中第k个独一无二的字符串。如果少于k个独一无二的字符串,那么返回空字符串?列出几种算法解决,用js实现

  2. 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的长度。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.