XIX
Задача о поиске элемента ⭐⭐
Дан упорядоченный массив чисел размером N
Нужно реализовать алгоритм поиска вхождения упорядоченного подмассива размера M
, где M << N
func isInclude(array int[], subarray []int) bool
assert(isInclude([1, 2, 3, 5, 7, 9, 11], []) == true)
assert(isInclude([1, 2, 3, 5, 7, 9, 11], [3, 5, 7]) == true)
assert(isInclude([1, 2, 3, 5, 7, 9, 11], [4, 5, 7]) == false)
Что хочется увидеть:
- Алгоритм со сложность быстрее чем
O(N)
по времени
По задаче "XVII Задача о поиске не отсортированного подмассива" - вы уж как то определитесь в формулировкой: либо результат это начальный и конечный индекс подмассива, который нужно убрать чтобы остался отсортированный массив, или результат начальный и конечный индекс подмассива который изменит индексы при сортировке!! Например мою функцию, которая возвращает {1,2} для массива array: []int{2, 1, 0, 3, 4, 5, 6, 7, 8, 9}, объявили неверной, хотя: {2, [1, 0,] 3, 4, 5, 6, 7, 8, 9} -> {2,3,4,5,6,7,8,9}
цитата:
"...К сожалению, тестовое задание решено неверно: не проходят тесты, пример
array: []int{2, 1, 0, 3, 4, 5, 6, 7, 8, 9},
expected: []int{0, 2}..."
и еще:
"...В ответ должны быть включены элементы, которые при сортировке поменяют свой индекс:
{[2, 1, 0], 3, 4, 5, 6, 7, 8, 9} -> {[0, 1, 2], 3, 4, 5, 6, 7, 8, 9}..."
как в известной поговорке: "чувствую, что где то нае*али но не пойму где"