Сообщение Re[4]: О собеседованиях на 700к/месяц от 27.06.2023 6:38
Изменено 27.06.2023 6:57 landerhigh
Re[4]: О собеседованиях на 700к/месяц
Здравствуйте, cppguard, Вы писали:
C>Здравствуйте, landerhigh, Вы писали:
L>>Нет, там можно (и нужно) получить именно O(N+log(M))
L>>Имхо это может быть сложно увидеть сразу, но при попытке реализовать алгоритм станет очевидно.
C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.
Дело в том, что нет никакой необходимости проводить N поисков по M:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательноси на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.
C>Здравствуйте, landerhigh, Вы писали:
L>>Нет, там можно (и нужно) получить именно O(N+log(M))
L>>Имхо это может быть сложно увидеть сразу, но при попытке реализовать алгоритм станет очевидно.
C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.
Дело в том, что нет никакой необходимости проводить N поисков по M:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательноси на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.
Re[4]: О собеседованиях на 700к/месяц
Здравствуйте, cppguard, Вы писали:
C>Здравствуйте, landerhigh, Вы писали:
L>>Нет, там можно (и нужно) получить именно O(N+log(M))
L>>Имхо это может быть сложно увидеть сразу, но при попытке реализовать алгоритм станет очевидно.
C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.
Дело в том, что нет никакой необходимости проводить N поисков по M:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.
C>Здравствуйте, landerhigh, Вы писали:
L>>Нет, там можно (и нужно) получить именно O(N+log(M))
L>>Имхо это может быть сложно увидеть сразу, но при попытке реализовать алгоритм станет очевидно.
C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.
Дело в том, что нет никакой необходимости проводить N поисков по M:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.