Van*_*ril 7 c++ algorithm data-structures
我已经给了很多想法,但实际上并没有想出一些东西.
假设我想要X列的元素集合可以按任何列和O(m*n)下的任何行进行排序,并且还能够插入或删除O(m + n)或更少的行...是否可能？
我想出的是链接网格,其中节点插入到向量中,因此我有它们的索引,并索引第一行和列以消除在任何一个方向遍历列表的必要性.用我的方法我已经实现了上述复杂性,但我只是想知道是否有可能通过非常数因子进一步降低这一点.
可排序性示例:
1 100 25 34
2 20 15 16
3 165 1 27
按第3行排序:
25 1 34 100
15 2 16 20
1 3 27 165
按第1列排序:
1 3 27 165
15 2 16 20
25 1 34 100
我会创建两个索引数组,一个用于列,一个用于行.所以对你的数据
1 100 25 34
2 20 15 16
3 165 1 27
您创建两个数组:
cols = [0, 1, 2, 3]rows = [0, 1, 2]然后,当您想要按第3行对矩阵进行排序时,保持原始矩阵不变,但只需相应地更改indices数组:
cols = [2, 0, 3, 1]rows = [0, 1, 2]现在的诀窍是用一个间接访问你的矩阵.因此,不要通过访问它来m[x][y]访问它m[cols[x]][rows[y]].在执行rows/cols数组的重新排序时,还必须使用m [cols [x]] [rows [y]].
这种方式排序是m[cols[x]][rows[y]],访问是O(n*log(n)).
对于数据结构,我会使用一个包含指向另一个数组的链接的数组:
+-+
|0| -> [0 1 2 3 4]
|1| -> [0 1 2 3 4]
|2| -> [0 1 2 3 4]
+-+
要插入一行,只需将其插入最后一个位置O(1),然后使用正确的位置相应地更新索引数组.例如,当rows是rows你想在前面,将其插入,行会变成[0, 1, 2].这样插入一行即可[3, 0, 1, 2].
要插入列,还要将其添加为最后一个元素,并相应地更新cols.插入一列是O(n),行是O(m).
删除也是O(n)或者O(n),您只需用最后一个删除要删除的列/行,然后从索引数组中删除索引.