arrays - 如果数组中的两个连续数字相等，如何缩小数组然后删除一个并增加另一个

Question

如果数组中的两个连续数字相等，如何缩小数组然后删除一个并增加另一个

示例 1：

int a[6]={2,2,3,4,4,4};

// Output: 6

示例 2：

int b[7]={1,2,2,2,4,2,4};

// Output: {1,3,2,4,2,4}

Answer 1

lst = [2,2,3,4,4,4]
    
def shrink(lst):
    idx = 0
    while len(lst) > idx+1:
        a, b = lst.pop(idx), lst.pop(idx)

        if a == b:
            lst.insert(idx, a+1)
            idx = 0
        else:
            lst.insert(idx, b)
            lst.insert(idx, a)
            idx += 1

shrink(lst)
print(lst)

印刷：

[6]

---

用于[5, 5, 5, 1]打印[6, 5, 1]

Answer 2

这可以在接近线性的时间内完成，如下所示：

a = [2, 2, 3, 4, 4, 4]
b = [1, 2, 2, 2, 4, 2, 4]
c = [5, 5, 5, 1]

def shrink_array(a):
    res = []
    
    for i in range(1, len(a)+1):
        if i < len(a) and a[i] == a[i-1]: # if equal to previous
            a[i] += 1 # increment and move on
        else:
            if len(res) > 0 and res[-1] == a[i-1]: # if equal to last in res
                res[-1] += 1 # increment last in res
            else:
                res.append(a[i-1]) # add to res

        while len(res) > 1 and res[-1] == res[-2]: # shrink possible duplicates
            res[-2] += 1
            del res[-1]
        
    return(res)

for arr in [a, b, c]:
    print(shrink_array(arr))

输出：

[6]
[1, 3, 2, 4, 2, 4]
[6, 5, 1]