Как оптимально изменить поля 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

Предполагая, что числа разбросаны редко, вы можете сделать следующее:

• Вычислить целевой индекс в каждом элементе в исходном списке
• Вычислить самое длинное увеличениеподпоследовательность (O (nlogn)) по индексам
  • Оставьте OrderNum неизменным для элементов в вычисленной подпоследовательности
  • Измените OrderNums остальных элементов так, чтобы они попадали всоответствующие промежутки

Это предполагает, что между исходными OrderNums достаточно места.После нескольких таких переупорядочений вам может понадобиться перенастроить цифры, чтобы это имело место.