如何以 O(n) 时间高效插入二维排序矩阵
我需要插入一个排序的二维 nxn 矩阵，插入应该在 O(n) 内实现。但条件是整个矩阵未排序，仅行和列排序。
示例：
9 10 12 14
11 12 14 15
21 22 28 Null
23 24 Null Null
将新元素插入到上述矩阵后，矩阵应按行和列排序。
我的方法
我正在考虑做一些事情，比如在矩阵 (3, 3) 的末尾插入新元素，从那里我将检查 (3, 3-1) 和 (3-1, 3) 如果 (3, 3) <，我会将 (3, 3) 与 max[(3, 3-1), (3-1, 3)] 交换max[(3, 3-1), (3-1, 3)]，就像我将遍历整个矩阵，直到不需要交换为止。
如果有更好的方法，请告诉我。
I need to insert into a sorted 2-D n x n matrix, insertion should be achieved in O(n). but the condition is the whole matrix is not sorted, only rows and columns are sorted.
example:
9 10 12 14
11 12 14 15
21 22 28 Null
23 24 Null Null
after inserting a new element into the above matrix the matrix should be sorted in row and column wise.
My approach
I am thinking to do something like inserting the new element at the end of the matrix (3, 3), from there I will check (3, 3-1) and (3-1, 3) I will swap (3, 3) with max[(3, 3-1), (3-1, 3)] if (3, 3) < max[(3, 3-1), (3-1, 3)], like that I will traverse the whole matrix until there is no swapping is required.
Please let me know If there is a better way to do it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论