Сортировка на основе непрерывности данных - PullRequest
Новая
       5

Сортировка на основе непрерывности данных

0 голосов
/ 12 октября 2018

Предполагая, что есть класс данных, как псевдокод ниже. 

class Data
    decimal Addition
    decimal Result
end

И есть массив или список данных.Например: 

[0] --> { Addition = 0.0, Result = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0 }
[2] --> { Addition = 5.0, Result = 65.0 }
[3] --> { Addition = 30.0, Result = 80.0 }
[4] --> { Addition = -20.0, Result = 60.0 }

Результат i-го члена должен быть равен Результату (i-1) -го члена + Добавление i-го члена.В приведенном выше примере порядок должен быть 0, 1, 3, 4, 2, как показано ниже: 

[0] --> { Addition = 0.0, Result = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0 }
[3] --> { Addition = 30.0, Result = 80.0 }
[4] --> { Addition = -20.0, Result = 60.0 }
[2] --> { Addition = 5.0, Result = 65.0 }

Если есть 2 или более элемента с одинаковым результатом, то самый ранний элемент массива будетприоритеты.Как сделать O (N lg N) сортировку для этого типа данных?

Ответы [ 2 ]

0 голосов
/ 12 октября 2018

Предполагая, что последовательность должна начинаться с данных со значением Addition = 0.0.Мы можем найти, что, найдя предыдущее значение для каждого из данных, используя 

PreviousValue = Addition-Result

, например, 

[0] --> { Addition = 0.0, Result = 60.0, PreviousValue = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0, PreviousValue = 60.0 }
[2] --> { Addition = 5.0, Result = 65.0, PreviousValue = 60.0 }
[3] --> { Addition = 30.0, Result = 80.0, PreviousValue = 50.0 }
[4] --> { Addition = -20.0, Result = 60.0, PreviousValue = 80.0 }

И затем мы можем O (n lg n) отсортировать этот список по его предыдущему значению.как следует 

[3] --> { Addition = 30.0, Result = 80.0, PreviousValue = 50.0 }
[0] --> { Addition = 0.0, Result = 60.0, PreviousValue = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0, PreviousValue = 60.0 }
[2] --> { Addition = 5.0, Result = 65.0, PreviousValue = 60.0 }
[4] --> { Addition = -20.0, Result = 60.0, PreviousValue = 80.0 }

После этого, начиная с начального узла (данные со значением Addition = 0.0), мы можем использовать O (lg n) двоичный поиск в отсортированном списке, чтобы найти данные для следующей последовательности, результатравно текущему предыдущему значениюСледовательно, эта проблема может быть решена с O (n + 2 n lg n) сложностью

0 голосов
/ 12 октября 2018

Данные по сути являются графиком.Перепишите каждый элемент от, до: 

[0] --> { Addition = 0.0, Result = 60.0 }   --> { From =  0.0, To = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0 } --> { From = 60.0, To = 50.0 }
[2] --> { Addition = 5.0, Result = 65.0 }   --> { From = 60.0, To = 65.0 }
[3] --> { Addition = 30.0, Result = 80.0 }  --> { From = 50.0, To = 80.0 }
[4] --> { Addition = -20.0, Result = 60.0 } --> { From = 80.0, To = 60.0 }

Маркируйте узлы графа, используя значения, и каждый элемент является ребром.

Теперь перейдите к чтению алгоритмов обхода графа и эйлеровых путей.

...