Блог

   0 1 2 3 4 5 6
0{1,2,1,2,1,5,5}
1{5,4,5,4,5,1,1}
2{2,4,2,4,2,1,1}
3{1,2,1,2,1,1,1}
4{4,4,4,4,4,1,1}
5{2,4,2,4,2,2,2}
  

вывод: {{0,2,4}, {1,3}, {5,6}} ( может использовать любую структуру данных)

Допустим, существует вложенный массив, подобный приведенному выше. Если бы мы хотели найти индексы столбцов, которые содержат одинаковые точные числа в том же порядке (например, столбец 0, 2, 4 с (1,5,2,1,4,2) и столбец 1, 3 с (2,4,4,2,4,4), а столбец 5, 6 с (5,1,1,1,1,2), как мы можем эффективно выполнить это? Потребуется ли для этого динамическое программирование?

Заранее спасибо.

Вы можете просто перебирать столбцы, сохраняя хэш-карту столбцов, которые вы видели до сих пор. Вот реализация на python:

 x = [[1, 2, 1, 2, 1, 5, 5], 
     [5, 4, 5, 4, 5, 1, 1], 
     [2, 4, 2, 4, 2, 1, 1], 
     [1, 2, 1, 2, 1, 1, 1], 
     [4, 4, 4, 4, 4, 1, 1], 
     [2, 4, 2, 4, 2, 2, 2]]
seen_before = {}
for v, col in enumerate(zip(*x)):
    if tuple(col) not in seen_before:
        seen_before[tuple(col)] = [v]
    else:
        seen_before[tuple(col)].append(v)
  

Это решает проблему за линейное время. Я надеюсь, что этого достаточно для вас.