Задание 1 Нечетные вхождения в массиве
Решение:
Конечно, мы можем использовать какой-нибудь индексный массив или хеш-таблицу, либо отсортировать данный массив, чтобы пометить парные элементы или ускорить их поиск. Но все эти подходы потребляют много памяти и/или нуждаются во многих проходах по массиву.
Лучшее решение здесь основано на «битовой магии». ИМХО это пример немного гениальной проницательности.
Он основан на том, что операция XOR имеет следующее свойство:
N XOR N = 0 N XOR 0 = N
Алгоритм:
- Объявите переменную, которая будет содержать результат
- Установите эту переменную в 0
- XOR каждого числа из данного массива с этой переменной.
- Возвращает непарное число из переменной.
В С++ это выглядит так:
int get_odd_occurrence(vector<int> & v) {
int res = 0;
for(auto i: v) {
res ^= i;
}
return res;
}
Давайте посмотрим, что произойдет с битами, если мы применим этот алгоритм к следующему массиву:
4, 3, 4, 2, 2
Двоичное представление чисел из массива:
4 = 0100, 3 = 0011, 2 = 0010
Итерации алгоритма:
0000 ^ 0100 = 0100 = 4 0100 ^ 0011 = 0111 = 7 0111 ^ 0100 = 0011 = 3 0011 ^ 0010 = 0001 = 1 0001 ^ 0010 = 0011 = 3
Как видите, второе число из пары сбрасывает биты, которые были установлены первым числом из пары. Даже если они идут не сразу друг за другом. Наконец, все биты, которые были установлены в 1, будут сброшены для каждого парного числа, и мы будем иметь в переменной значение единственного непарного числа.
Если вы вообще не хотите использовать дополнительную память, но вам не нужно хранить значения в массиве, вы можете сохранять промежуточные значения прямо в массиве. Например вот так:
int get_odd_occurrence(vector<int> & v) {
// destructive solution
for(auto i = 1; i < v.size(); ++i) {
v[i] ^= v[i-1];
}
return v.back();
}
Задание 2 Циклическое вращение
Решение:
Существует несколько быстрых алгоритмов вращения массива. ИМХО, лучшее решение, которое имеет смысл иметь в виду, - это очень быстрый и в то же время очень простой алгоритм. Это очень легко понять и запомнить. И вдобавок этот алгоритм потребляет всего несколько байтов для дополнительных переменных и переменной, которая хранит один элемент данного массива.
Алгоритм:
Для поворота массива на заданное количество элементов достаточно поменять местами левую часть массива после заданных элементов и правую часть массива, содержащую заданное количество элементов, а затем повернуть весь массив.
Например, возьмем массив: 1, 2, 3, 4, 5, 6, 7, 8, 9. Нам нужно повернуть этот массив на 3 элемента вправо.
1. Разделите этот массив на две части: 1, 2, 3, 4, 5, 6 и 7, 8, 9
2. Повернуть левую часть: 6, 5, 4, 3, 2, 1
3. Повернуть правую часть: 9, 8, 7
Теперь весь массив выглядит так: 6, 5, 4, 3, 2, 1, 9, 8, 7
4. Поверните весь массив: 7, 8, 9, 1, 2, 3, 4, 5, 6
Хорошо написать часть вращения как отдельную функцию. Для работы с любыми видами векторов я сделал его шаблонным.
template < class T >
void reverse(vector<T> & v, size_t begin, size_t end) {
while(begin < end) {
auto temp = v[begin];
v[begin] = v[end];
v[end] = temp;
begin++;
end--;
}
}
Теперь функция вращения выглядит тривиально:
template < class T >
void right_rotate_reverse(vector<T> & v, size_t rot_dist) {
auto v_size = v.size();
reverse(v, v_size - rot_dist, v_size-1);
reverse(v, 0, v_size-1 - rot_dist);
reverse(v, 0, v_size-1);
}
Но для обработки всех угловых случаев и устранения ненужных поворотов нам нужно добавить еще немного кода. Вот так выглядит завершенная функция вращения:
template < class T >
void right_rotate_reverse(vector<T> & v, size_t rot_dist) {
auto v_size = v.size();
if( (v_size < 2) || (rot_dist == 0)) { return; }
if(( (rot_dist % v_size) == 0)) {
return;
}
else if( v_size < rot_dist) {
rot_dist %= v_size;
}
reverse(v, v_size - rot_dist, v_size-1);
reverse(v, 0, v_size-1 - rot_dist);
reverse(v, 0, v_size-1);
}
Не слишком сложно не так ли?
Левое вращение выглядит почти так же:
template < class T >
void left_rotate_reverse(vector<T> & v, size_t rot_dist) {
auto v_size = v.size();
if( (v_size == 2) || (rot_dist == 0) || (rot_dist == v_size) ) {
return;
}
if( v_size < rot_dist) { rot_dist -= v_size; }
reverse(v, 0, rot_dist - 1);
reverse(v, rot_dist, v_size-1);
reverse(v, 0, v_size-1);
}
Очень простой.
Но действительно самый быстрый алгоритм общего назначения, основанный на перестановке частей массива.
Он немного быстрее предыдущего, но ИМХО он сложнее для понимания и при его написании легко сделать ошибки. Так что рекомендую запомнить предыдущий, если он вам нужен для интервью.
Алгоритм:
1. Разделить заданный массив на две части, как в предыдущем алгоритме.
2. Определить, какая часть массива длиннее.
3. Разделите самую длинную часть на две части. Одна часть с размером самой короткой части другая является остатком.
4. Поменяйте местами самую короткую часть с самой длинной частью того же размера.
5. Рекурсивно повторяйте шаги 2–4, пока обе стороны не будут иметь одинаковый размер.
Например, возьмем массив: [1, 2, 3, 4, 5, 6, 7, 8, 9]. Нам нужно повернуть этот массив на 3 элемента вправо.
1. Разделите этот массив на две части: [1, 2, 3, 4, 5, 6] и [7, 8, 9]
2. Определите, что левая часть длиннее правой.
3. Разделите левую часть на две части, причем одна часть будет иметь тот же размер, что и правая часть.
4. [1, 2, 3] и [4, 5, 6]
5. Поменяйте местами правую часть и часть левой части с одинаковым размером:
[7, 8, 9], 4, 5, 6, [1, 2, 3]
6. Теперь у нас есть [7, 8, 9] на последнем месте, поэтому сосредоточьтесь на остальных элементах массива: [4, 5, 6, 1, 2, 3]
7. Убедитесь, что обе стороны имеют одинаковый размер, поэтому поменяйте их местами. Результат [1, 2, 3, 4, 5, 6]
8. Это конец мой друг :) Весь массив выглядит так:
[7, 8, 9, 1, 2, 3, 4, 5, 6].
Именно так, как нам нужно.
Обычно этот алгоритм самый быстрый, но он может быть медленнее, чем предыдущий, если у вас есть массив, значительно превышающий объем доступной оперативной памяти. В этом случае этот алгоритм заставит вашу операционную систему подкачивать страницы памяти очень часто, потому что он меняет местами элементы всего массива. Но предыдущий алгоритм реверсирует элементы более последовательно.
Реализация левого поворота на C++ выглядит так:
template < class T >
void swap(vector<T> & v, size_t a, size_t b, size_t size ) {
for(size_t i = 0; i < size; ++i) {
T temp = v[a + i];
v[a + i] = v[b + i];
v[b + i] = temp;
}
}
template < class T >
void left_rotate_swap(vector<T> & v, size_t rot_dist) {
auto v_size = v.size();
auto i = rot_dist, j = v_size - rot_dist;
while (i != j) {
if (i > j) {
swap(v, rot_dist-i, rot_dist, j);
i = i-j;
}
else {
swap(v, rot_dist-i,rot_dist+j-i, i);
j = j-i;
}
}
swap(v, rot_dist-i, rot_dist, i);
}
Если вы думаете, что это так же просто, как и предыдущее, попробуйте написать функцию вращения вправо самостоятельно.
Вернитесь к оглавлению.
