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

原始解决方案使用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个字符.如果重复将跳过字符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

/* 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),所以时间复杂度不变.