Таким образом, в основном, у вас есть отсортированный список точек, которые составляют всю веревку, и вы получили две произвольные точки из этого списка, и вам поручено вернуть подсписок, который существует между этими двумя точками.
Я собираюсь сделать предположение, что начальная и конечная точки, которые предоставляются, точно совпадают с точками в отсортированном списке (в противном случае возникает множество проблем, особенно если веревка может быть сколь угодно тонкой и проходит по начальной / конечной точкам несколько раз).
Это означает, что все, что вы действительно ищете, это индексы двух предоставленных координат. Или индекс один, а ответ «вторая координата направо или налево?».
Простое решение O (n) для этого будет:
For each index in array
coord = array[index]
if (coord == point1)
startIndex = index
if (coord == point2)
endIndex = index
if (endIndex < startIndex)
swap(startIndex, endIndex)
return array.sublist(startIndex, endIndex)
Или, если вы хотите оптимизировать повторяющиеся запросы, я бы предложил подход, основанный на хешировании, в котором вы отображаете каждую координату в индекс в массиве. Что-то вроде:
//build the map (do this once, at init)
map = {}
For each index in array
coord = array[index]
map[coord] = index
//find a sublist (do this for each set of start/end points)
startIndex = map[point1]
endIndex = map[point2]
if (endIndex < startIndex)
swap(startIndex, endIndex)
return array.sublist(startIndex, endIndex)
Это O (n) для построения карты, но как только она будет построена, вы можете определить подсписок между любыми двумя точками в O (1). Предполагая, конечно, эффективную хэш-карту.
Обратите внимание, что если мое предположение не выполняется, то те же решения по-прежнему могут использоваться, при условии, что в качестве первого шага вы берете предоставленные начальную и конечную точки и определяете точки в массиве, которые лучше всего соответствуют каждой из них. Как уже отмечалось, если вам не даны некоторые ограничения в отношении толщины веревки, то интерполяция от произвольной координаты до той, которая фактически является частью веревки, может быть в лучшем случае только догадкой.