lower_bound и upper_bound - встроенные функции бинарного поиска.
lower_bound - функция, которая за логарифмическое время в отсортированном массиве находит наименьший элемент, который больше заданного значения k или равен ему.
В качестве аргументов принимает границы массива и значение k.
Возвращает итератор на найденный элемент или на конец (невключенный) массива, если такого элемента не существует.
Подробнее можете прочитать в документации.
upper_bound - функция, которая за логарифмическое время в отсортированном массиве находит наименьший элемент, который строго больше заданного значения k.
В качестве аргументов принимает границы массива и значение k.
Возвращает итератор на найденный элемент или на конец (невключенный) массива, если такого элемента не существует.
Подробнее можете прочитать в документации.
Стоит уточнить, что применение данных функций на set или multiset работает не за логарифмическое время по причине отсутствия у вышеупомянутых коллекций random access итераторов.
Однако у этих коллекций есть соответствующие встроенные методы (то есть нужно использовать их "через точку").
Примеры:
vector a = { 0, 1, 3, 5, 7 };
vector::iterator it;
it = lower_bound(a.begin(), a.end(), 4);
// *it == 5
it = lower_bound(a.begin(), a.end(), 5);
// *it == 5
it = lower_bound(a.begin(), a.end(), 8);
// it == a.end()
it = upper_bound(a.begin(), a.end(), 4);
// *it == 5
it = upper_bound(a.begin(), a.end(), 5);
// *it == 7
it = upper_bound(a.begin(), a.end(), -1);
// *it == 0
// путем вычета итераторов можно получить индекс найденного элемента
int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
// ind == 3
// нужно использовать методы вместо функций для set и аналогичных коллекций
set s{ 1, 3, 5 };
set::iterator sit;
sit = s.lower_bound(3);
// *sit == 3
sit = s.upper_bound(3);
// *sit == 5
|
unique - функция, которая за линейное время сжимает все последовательности одинаковых подряд идущих элементов в один.
В качестве аргумента ей передаются границы массива, в пределах которых необходимо применить сжатие.
Возвращается же итератор на новый конец (не включительно) массива. Стоит быть внимательным с элементами, расположенными после нового конца, но до старого, так как они будут иметь неопределенное значение.
Подробнее можете прочитать в документации.
Если вы применяете эту функцию на vector, то удобно делать resize, используя возвращаемый результат (подробнее ниже).
Примеры:
vector a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
unique(a.begin(), a.end());
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// с помощью функции unique удобно делать
// вспомогательный массив для сжатия координат
a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
sort(a.begin(), a.end());
// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(unique(a.begin(), a.end()) - a.begin());
// a = [10, 41, 235, 500]
|
merge - функция, которая объединяет два отсортированных массива, а именно, за линейное время получает отсортированный массив, который состоит из элементов первого и второго массива.
Она принимает 5 аргументов: по две границы для каждого массива и левая граница места назначения (где будут расположены элементы результирующего массива).
Подробнее можете ознакомиться в документации.
Примеры:
// исходные массивы должны быть отсортированы
vector a = { 1, 3, 5, 7 };
vector b = { 2, 4, 6 };
// необходимо, чтобы место назначения имело достаточный размер
vector c(7);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// элементы могут повторяться
a = { 1, 2, 4, 4};
b = { 2, 3, 3, 3, 4, 4 };
c.resize(10);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
Данную функцию очень удобно использовать в контексте сортировки слиянием.
|
nth_element - функция, которая позволяет находить n-ый элемент в массиве в отсортированном порядке за линейное время.
Функция принимает левую границу массива, итератор на позицию, значение которой в отсортированном порядке необходимо найти и правую границу массива.
После применения функции на указанном по итератору месте будет находиться необходимое значение, при этом остальные значения приобретут хаотичный порядок, но левее n-ого будут значения не больше его, а правее не меньше. То есть стоит понимать, что эта функция рушит исходный порядок элементов.
Подробнее можете прочитать в документации (https://www.cplusplus.com/reference/algorithm/nth_element/).
Пример:
vector a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// ищем элемент по индексу 4
// обратите внимание на порядок аргументов
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// где # <= 4 и 4 <= $
|
Перестановка длины n - это упорядоченный набор без повторений чисел 1, 2, ..., n. Например, [3, 1, 2] и [5, 4, 3, 2, 1] являются перестановками, а [1, 2, 1, 3] и [1, 2, 4] не являются.
Если задача свелась к тому, что необходимо перебрать все перестановки длины n, то можно воспользоваться удобным механизмом в С++, который называется "next_permutation".
Подробно об этом можно прочитать в документации, но смысл в том, что эта функция изменяет переданный массив на последующую перестановку в лексикографическом порядке (что в целом понятно и ее названия).
Для использования next_permutation необходимо подключить библиотеку algorithm (т.е. прописать #include <algorithm> в начале программы)
Примеры:
vector arr;
arr = { 1, 2, 3 }; // массив равен [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // передаем в функцию весь массив
// теперь массив равен [1, 3, 2]
arr = { 2, 3, 1 }; // массив равен [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // передаем в функцию весь массив
// теперь массив равен [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // можно применить функцию на части массива, но на практике такое редко требуется
// теперь массив равен [3, 2, 1]
При этом функция имеет булево возвращаемое значение, которое равно true, если была сгенерирована следующая перестановка и false, если следующей не было (случай, когда в функцию передается максимальная перестановка в лексикографическом порядке).
Это делает возможным использование функции в цикле, что позволит нам перебирать сразу все перестановки. Из-за 0-индексации на практике зачастую удобнее работать с перестановкой чисел от 0 до n - 1, хотя формально перестановка содержит числа от 1 до n. Но к счастью это не приводит к дополнительным накладкам в коде, т.к. функция next_permutation адаптирована к 0-индексированным перестановкам (и даже к повторяющимся элементам в массиве, но подробнее вы можете выяснить самостоятельно).
В целом код перебора всех перестановок выглядит следующим образом:
int n; // размер перестановки
vector perm(n); // perm - сокращение от "permutation", т.е. "перестановка"
for (int i = 0; i < n; i++)
perm[i] = i; // инициализируем начальную перестановку 0, 1, ..., n - 1
do {
// внутри цикла обрабатываем текущую перестановку
} while (next_permutation(perm.begin(), perm.end())); // если не существует следующей перестановки, то закончим цикл
Данный код работает за O(n! * f(n)), где f(n) - время, за которое вы обрабатываете одну конкретную перестановку.
|