在 O(1) space 中将列表中的 m 次重复数字收缩为 n 次重复 (n<m)

Question

我想写一个 python 3.7 函数，它有一个排序的数字列表作为输入，一个数字 n 是每个整数可以重复和修改的最大数量列表到位，以便任何重复超过 n 次的数字将被削减为 n 重复，并且应该在 O(1) space 中完成，否允许额外的数据结构（例如 set()）。特例 - 删除 n = 1 中的重复项。示例：

dup_list = [1, 1, 1, 2, 3, 7, 7, 7, 7, 12]
dedup(dup_list, n = 1)
print(dup_list)
[1, 2, 3, 7, 12]

dup_list = [1, 1, 1, 2, 3, 7, 7, 7, 7, 12]
dedup(dup_list, n = 2)
print(dup_list)
[1, 1, 2, 3, 7, 7, 12]

dup_list = [1, 1, 1, 2, 3, 7, 7, 7, 7, 12]
dedup(dup_list, n = 3)
print(dup_list)
[1, 1, 1, 2, 3, 7, 7, 7, 12]

案例n = 1很简单，代码如下（代码取自Elements of Prograqmming Interviews, 2008, page 49，除了最后一行return dup_list[:write_index]）：

def dedup(dup_list):                                                                                                       
    if not dup_list:                                                                                                       
        return 0                                                                                                           
                                                                                                                           
    write_index = 1                                                                                                        
    for i in range(1, len(dup_list)):                                                                                      
        if dup_list[write_index-1] != dup_list[i]:                                                                         
            dup_list[write_index] = dup_list[i]                                                                            
            write_index += 1                                                                                               
                                                                                                                           
    return dup_list[:write_index]

Answer 1

这应该有效：

def dedup2(dup_list, n):
    count = 1
    list_len = len(dup_list)
    i = 1
    while i < list_len:
        if dup_list[i - 1] != dup_list[i]:
            count = 1
        else:
            count += 1
            if count > n:
                del(dup_list[i])
                i -= 1
                list_len -= 1
        i += 1
    return dup_list

print(dedup2([1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 8, 9], 1))

在 O(1) space 中将列表中的 m 次重复数字收缩为 n 次重复 (n<m)

Contract m-repeated numbers in list to n-repeated (n<m) in place in O(1) space

array-algorithms

python-3.7