algorithm - 如何以最佳方式更改 item.OrderNum 字段以匹配列表顺序

Question

我有包含 OrderNum 字段的对象列表。

OrderNum 字段必须匹配列表顺序(但不需要连续)。

简单的解决方案。当列表顺序更改时重置每个 OrderNum:

for (int i = 0; i < list.length; i++) {
    list[i].OrderNum = i;
}

但由于 OrderNum 是存储在 SQL 中的，重置的 OrderNum 越小越好。当必须重置 OrderNum 时，更改可能会很大。有 32 位可供使用。有序列表通过以下方式检索:

SELECT * FROM orderable_items ORDER BY order_num;

实际的编程语言是 C#。

Answer 1

假设数字间隔稀疏，您可以执行以下操作:

• 计算原始列表中每个元素的目标索引
• 计算longest increasing subsequence (O(nlogn)) 在索引上
  • 保留计算子序列中元素的 OrderNum 不变
  • 更改其余元素的 OrderNums，使它们落入适当的间隙

这假设原始 OrderNums 之间有足够的空间。在几次这样的重新排序之后，您可能需要重新调整数字以使其成为这种情况。