Сложный уровень
Легкий
Спросил в
Facebook, Amazon, Uber, Bloomberg, Linkedin, Paytm
Обсуждены три решения
- Подход грубой силы - использование лишнего места
- Подход с использованием двух указателей - двойное сканирование
- Подход с использованием двух указателей - одно сканирование
Ключевые выводы после прочтения этого блога
- Эффективное решение - это вариант подхода с двумя указателями, когда указатели движутся в одном направлении.
- Хорошая задача - изучить оптимизацию, улучшив сложность пространства и уменьшив лишний обход.
- Мы можем использовать аналогичные идеи для решения других проблем с кодированием.
- Хорошая задача для новичков, чтобы начать писать код.
Давайте разберемся в проблеме
Для массива X [] из n элементов, заполненных несколькими целыми числами, некоторые из которых являются нулями, напишите программу для перемещения всех нулей в конец.
Примеры
Input: X[] = [4, 8, 6, 0, 2, 0, 1, 15, 12, 0] Output: [4, 8, 6, 2, 1, 15, 12, 0, 0, 0] Input: X[] = [0, 3, 5, 9, 0, 0, 23, 2] Output: [3, 5, 9, 23, 2, 0, 0, 0]
Подход грубой силы: использование лишнего места
Одна из основных идей - сначала пройти по входному массиву X [] и сохранить все ненулевые элементы в дополнительной памяти Y [] размера n. Теперь заполните оставшееся пустое пространство Y [] нулями и верните его как результат.
- Инициализируйте два указателя i и j, где указатель i предназначен для обхода входного массива X [], а j - для хранения значений в Y []. Оба указателя движутся в одном направлении.
- Во время обхода, когда мы находим ненулевой элемент x [i], сохраняем его в Y [j] и увеличиваем как i, так и j. В противном случае просто увеличьте указатель i.
Псевдокод алгоритма
int[] moveZeroesEnd(int X[], int n)
{
int Y[n]
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if (X[i] != 0)
{
Y[j] = X[i]
j = j + 1
}
}
while (j < n)
{
Y[j] = 0
j = j + 1
}
return Y
}
Анализ алгоритмов
Сложность времени = Сложность времени обхода X [] и сохранения ненулевых элементов в Y [] + Сложность времени сохранения нулей в Y [] = O (n) + O (n) = O ( п). Другими словами, в худшем случае мы выполняем один обход обоих массивов.
Сложность пространства = O (n) для дополнительного пространства Y [].
Подход с использованием двух указателей - двойное сканирование
Теперь критический вопрос: можем ли мы дополнительно оптимизировать вышеупомянутый алгоритм, чтобы уменьшить сложность пространства или решить проблему на месте? Давай подумаем!
Мы можем использовать описанный выше подход, но вместо того, чтобы хранить его в дополнительном пространстве, мы можем изменить порядок нулевых и ненулевых элементов во входном массиве. Вот основные шаги -
- Обходите входной массив, используя два указателя i и j, где i - для обхода массива, а j - для отслеживания последнего индекса ненулевого элемента.
- Всякий раз, когда мы встречаем ненулевой элемент, мы перемещаем его в начало X [], т.е. если (X [i]! = 0), мы обновляем X [j] = X [i]. Мы также увеличиваем i и j на 1. В противном случае пропускаем нулевые элементы и перемещаем указатель i на 1.
- После всего процесса все элементы в X [0… j-1] являются ненулевыми элементами. Теперь снова переместите X [] от j к n-1 и заполните его нулями. (Подумайте!)
Псевдокод алгоритма
void moveZeroEnd(int X[], int n)
{
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if (X[i] != 0)
{
X[j] = X[i]
j = j + 1
}
}
while (j < n)
{
X[j] = 0
j = j + 1
}
}
Анализ алгоритмов
Сложность по времени (в худшем случае) = Сложность по времени прохождения X [] для ненулевых элементов + Сложность по времени прохождения X [] для заполнения нулей = O (n) + O (n) = На)
Мы решаем эту проблему на месте. Космическая сложность = O (1)
Использование подхода с двумя указателями - одно сканирование
Можем ли мы дополнительно оптимизировать описанный выше подход и решить его всего за один обход? Можем ли мы сократить второй обход, чтобы в итоге заполнить ноль? Давай подумаем!
В приведенном выше методе вместо присвоения X [j] X [i], если мы поменяем местами оба элемента, нам не нужно будет заполнять остальную часть массива нулями в конце. Все ненулевые элементы будут перемещены в конец за счет подкачки. Эта идея аналогична алгоритму разбиения быстрой сортировки.
Псевдокод алгоритма
void moveZeroEnd(int X[], int n)
{
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if(X[i]!= 0)
{
swap(X[j], X[i])
j = j + 1
}
}
}
Анализ алгоритмов
Мы делаем только один обход, где сравнение и замена являются критическими операциями. Сложность времени = O (n), сложность пространства = O (1)
Возможные вопросы интервьюера
- Можем ли мы, используя аналогичный подход, отсортировать массив, содержащий элементы только с двумя повторяющимися значениями? Как мы решим эту проблему при повторении трех значений?
- Какова будет полная операция подкачки в наихудшем сценарии при подходе с одним обходом?
- Сохраняется ли относительный порядок ненулевых элементов в вышеуказанных подходах?
- Во втором подходе, почему мы снова обходим, чтобы сохранить нули до конца входного массива?
- Можно ли решить эту проблему другим подходом? Можем ли мы использовать два указателя в противоположном направлении?
- Сохранят ли указанные выше подходы порядок ненулевых элементов?
Предлагаемые проблемы для решения
- Удвойте первый элемент и переместите ноль в конец
- Разделить четные и нечетные числа
- Разделить нули и единицы в массиве
- Переместите все значения, равные K, в конец массива
- Минимальные свопы, необходимые для сортировки массива в порядке возрастания
- Разделите массив так, чтобы сумма двух подмассивов была одинаковой.
- Проверить наличие пары в массиве с заданной суммой
Если у вас есть идеи / вопросы / сомнения / отзывы, оставьте комментарий ниже или напишите нам по адресу [email protected]. Наслаждайтесь обучением, наслаждайтесь кодированием, наслаждайтесь алгоритмами!
Первоначально опубликовано на www.enjoyalgorithms.com/coding-interview
