Дано три отсортированных массива с плавающей точкойa[], b[], а такжеc[]разработать линейный алгоритм, чтобы найти три целых числаi, j, а такжеk такой, что|a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]| это минимум.

У меня есть решение, но я не думаю, что оно является линейным. Это то, что я имею сейчас:

 assume minDiff = // some huge value

 for each entry in 'a'
   find an entry closest to it in 'b' and call it 'closestToA'
   find an entry closest to 'closestToA' in 'c' and call it 'closestToB'
   compute the diff: 
         int currDiff = Math.abs(a[i] - closestToA) + Math.abs(closestToA - closestToB) + Math.abs(closestToB - a[i]);
   Replace minDiff with currDiff, if currDiff < minDiff

Прежде всего, я хотел бы знать, есть ли лучшее решение? Если нет, то прав ли я, считая, что это решение не имеет линейной сложности? Ближайшее число можно найти с помощью бинарного поиска.

Вопрос из «Алгоритмы - 4-е изд.» Роберт Седжвик и Кевин Уэйн, и я готовлюсь к предстоящему интервью.

Несколько похожий вопрос:Совпадение трех или более ближайших чисел из массивов