主页 / 问题 / 1401539
Accepted
NEStenerus nester
Asked:2022-06-19 01:09:34 +0000 UTC2022-06-19 01:09:34 +0000 UTC

去除相互引用的对象的冗余值

  • 772

我有一个这样的列表（简化为通用实现）

a = [
['0', 11], 
['1', 3], 
None, 
['3', None], 
['4', 6], 
['5', None],
['6', None], 
['7', 10], 
None, 
['9', 4], 
['10', 11], 
['11', None]
]

其中，每个值要么是None，要么是一个列表，其中第一个元素是某种有效负载，第二个是None它所引用的元素的索引。例如：

print(a[a[0][1]])  # Выведет ['11', None]
print(a[a[1][1]])  # Выведет ['3', None]
print(a[a[4][1]])  # Выведет ['6', None]
print(a[a[7][1]])  # Выведет ['10', 11]
print(a[a[9][1]])  # Выведет ['4', 6]
print(a[a[10][1]]) # Выведет ['11', None]

任务是从给定列表中删除所有None元素，以便这些对索引的引用不会移出。并提到相同的元素。也就是说，让它看起来像这样：

a = [
['0', 9], 
['1', 2], 
['3', None], 
['4', 5], 
['5', None],
['6', None], 
['7', 8], 
['9', 3], 
['10', 9], 
['11', None]
]

同时，值也发生了变化，但是如果你得到一个具有特定数据的对象（每个列表的第一个元素）引用与以前相同的元素，尽管索引不同（注意显示的第一个元素数据的顺序与上述相同）：

print(a[a[0][1]])  # Выведет ['11', None]
print(a[a[1][1]])  # Выведет ['3', None]
print(a[a[3][1]])  # Выведет ['6', None]
print(a[a[6][1]])  # Выведет ['10', 9]
print(a[a[7][1]])  # Выведет ['4', 5]
print(a[a[8][1]]) # Выведет ['11', None]

索引发生了变化，但如您所见，数据本身并没有改变。我知道语言等，但我无法开发算法本身，我尝试按顺序遍历数组，我尝试以相反的顺序，但我的索引移出。你能告诉我如何得到我期望的结果吗？

python

0 个回答

  1. Best Answer

    也许还有更棘手的算法，但这样做很愚蠢 - 你遍历数组，删除不必要的元素并在字典中记住旧索引和新索引的对应关系，新索引等于旧的减去 delta，循环之前的增量 = 0，每次删除都会增加 1 在第一次循环之后，对数组进行第二次循环并替换字典引用中的索引：

    这是一个例子：

    def print_array(arr, text):
    print(text)
    for idx, item in enumerate(arr):
        if item and item[1]:
            print(idx, ':', item, '-->', arr[item[1]])
        else:
            print(idx, ':', item)


def delete_none(arr: list):
    old_new = dict()
    delta = 0
# Обратите внимание - первый цикл мы делаем по копии исходного списка
# это необходимо, поскольку мы удаляем элементы прямо в цикле.
# Если мы будем делать цикл по исходному списку, то элемент сразу за удаленным будет потерян для логики.
# Возможно, в python это как-то можно сделать по другому, но я не настолько его знаю
    for idx, item in enumerate(arr[:]):
        if not item:
            del arr[idx - delta]
            delta += 1
        else:
            old_new[idx] = idx - delta

    for item in arr:
        old_index = item[1]
        if old_index:
            if old_index in old_new:
                new_index = old_new[old_index]
                item[1] = new_index
            else:
                item[1] = None


def main():
    a = [
        ['0', 11],
        ['1', 3],
        None,
        ['3', None],
        ['4', 6],
        ['5', None],
        ['6', None],
        ['7', 10],
        None,
        ['9', 4],
        ['10', 11],
        ['11', None]
    ]
    print_array(a, 'Before')
    delete_none(a)
    print_array(a, 'After')


if __name__ == '__main__':
    main()
    • 2

相关问题