次数/值列表原地展开与Iterator：同一对象和辅助空间

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入[count,value,...]，count非负整数；value任意，输出复用同一个list对象。
• 允许list作为输出存储增长，额外辅助仅常数标量；不能同时要求输出变长却禁止任何容量增长。

解题路线

1. 通用基线扫描当前pair，保存count/value，删除这两格，再逐一在当前位置插入value并前移。未处理pair仍位于输出前缀之后，不会被覆盖。
2. 这个策略O(1)显式辅助但频繁搬移，最坏二次。若保证每count≥2，扩展总长后从尾部向前写可线性；混合count1/大count时简单尾写可能覆盖未读pair，不能直接声称通用。
3. Iterator保留pair下标/剩余次数/当前值，hasNext跳零run而不消耗一个输出值，next先确认再减次数。多次hasNext不改变下一值；输入迭代期间不允许修改。

手动走一遍

[4,3,2,1]原对象变[3,3,3,3,1,1]。[0,A,1,B,3,C]展开[B,C,C,C]；Iterator与原地版本输出一致，末尾next抛StopIteration。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def expand_inplace(a):
    if len(a)%2 or any(type(a[i]) is not int or a[i]<0 for i in range(0,len(a),2)):raise ValueError("count/value pairs required")
    position=0
    while position<len(a):
        count,value=a[position],a[position+1]
        del a[position:position+2]
        for _ in range(count):
            a.insert(position,value);position+=1
    return a


class RunIterator:
    def __init__(self,a):
        if len(a)%2 or any(type(a[i]) is not int or a[i]<0 for i in range(0,len(a),2)):raise ValueError("count/value pairs required")
        self.a=a;self.i=0;self.remaining=0;self.value=None

    def hasNext(self):
        while not self.remaining and self.i<len(self.a):
            self.remaining,self.value=self.a[self.i],self.a[self.i+1];self.i+=2
        return self.remaining>0

    def next(self):
        if not self.hasNext():raise StopIteration
        self.remaining-=1
        return self.value

复杂度

r pair、L展开长，通用插删最坏O((r+L)²)，辅助O(1)除输出容量。Iterator初始化校验O(r)，总输出O(r+L)，状态O(1)引用输入；单hasNext可能跳多个零run。

易错点与追问

容易失分的边界

• 用[value]*count构造巨大临时list不满足严格常数辅助。
• 新建一个list再赋给变量不是修改调用者的原对象。

继续深挖

• count全≥2怎样证明尾写指针从不覆盖未读pair？
• hasNext/getNext接口怎样区分空run、EOF和非法次数？