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

Question

给定一个表单的字符串AB2C3和一个int .然后k扩展字符串.任务是找到第k个元素.内存有限,因此无法展开整个字符串.你只需要找到第k个元素.ABABC3ABABCABABCABABC

我不知道如何去做.有人在编码面试中向我的朋友询问,我已经考虑了很多,但我没有得到有效的解决方案.

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最多只是旧值的一半.所以在最坏的情况下,我们会重新开始时间.log2k

虽然上述解决方案易于理解,但我们实际上可以做得更好.我们可以在扫描过去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 at以下字符.由于反向扫描O(N),时间复杂度不会改变.