c++ - 在扩展字符串中查找第 k 个元素

Question

给定一个 AB2C3 形式的字符串和一个 int k。将字符串展开为 ABABC3 然后 ABABCABABCABABC .任务是找到第 k 个元素。您的内存有限，因此无法展开整个字符串。您只需找到第 k 个元素。

我不确定该怎么做。在编码面试中被问到我的 friend ，我已经考虑了很多但我没有得到有效的解决方案。

Answer 1

更新一个O(1)空间和O(N)时间版本如下。见下文。

---

原始解决方案使用 O(1)空间和O(N log k)时间，在哪里n是未展开字符串的大小:

char find_kth_expanded(const char* s, unsigned long k) {
  /* n is the number of characters in the expanded string which we've
   * moved over.
   */
  unsigned long n = 0;
  const char *p = s;
  for (;;) {
    char ch = *p++;
    if (isdigit(ch)) {
      int reps = ch - '0';
      if (n * reps <= k)
        n *= reps;
      else {
        /* Restart the loop. See below. */
        k = k % n;
        p = s;
        n = 0;
      }
    }
    else if (ch == 0 || n++ == k)
      return ch;
  }
}

该函数只是简单地从左到右移动字符串，跟踪扩展字符串中经过的字符数。如果该值达到 k , 然后我们找到了 k扩展字符串中的第 th 个字符。如果重复会跳过字符 k , 然后我们减少 k到重复中的索引，然后重新开始扫描。

很明显它使用了O(1)空间。证明它运行在O(N log k) ，我们需要计算循环重新启动的次数。如果我们重新启动，那么 k≥n ，否则我们之前会返回 n 处的字符.如果k≥2n然后n≤k/2所以k%n≤k/2 .如果k<2n然后k%n = k-n .但是n>k/2 , 所以 k-n<k-k/2因此 k%n<k/2 .

所以当我们重新启动时，k 的新值最多是旧值的一半。所以在最坏的情况下，我们将重新启动 log<sub>2</sub>k次。

---

虽然上面的解决方案很容易理解，但实际上我们可以做得更好。我们可以在扫描过去 k 后向后扫描，而不是重新开始扫描。 (扩展)字符。在向后扫描期间，我们需要始终纠正 k通过以其模数为基础的段长度到当前段的范围:

/* Unlike the above version, this one returns the point in the input
 * string corresponding to the kth expanded character.
 */
const char* find_kth_expanded(const char* s, unsigned long k) {
  unsigned long n = 0;
  while (*s && k >= n) {
    if (isdigit(*s))
      n *= *s - '0';
    else
      ++n;
    ++s;
  }
  while (k < n) {
    --s;
    if (isdigit(*s)) {
      n /= *s - '0';
      k %= n;
    }
    else
      --n;
  }
  return s;
}

以上函数都不能正确处理乘数为 0 和 k 的情况。小于段的长度乘以 0。如果 0是一个合法的乘数，一个简单的解决方案是反向扫描最后一个 0 的字符串并从以下字符开始 find_kth_expanded。由于反向扫描是O(N) , 时间复杂度不变。