Привет. Задача не решаема за O(N), т.к. для поиска следующего вектора в худшем случае нужно log2(N) операций, естественно при предварительном создании отсортированного массива начал векторов — O(N*log2(N)). В сумме получаем O(2*N*log2(N)) == O(N*log2(N)). Хэш таблица не поможет — в худшем случае она может выродится и потребуется N операций для поиска — получаем O(N*N). Такае-же сложность и при поиске в лоб.