Выборка разных элементов массива
Выборка уникальных элементов массива
Задача – необходимо из неупорядоченного массива элементов выбрать все уникальные элементы. Осложним задачу следующим образом – попытаемся не использовать дополнительной памяти, а уникальные элементы класть в текущий массив.
Самый простой алгоритм: брать элемент и сравнивать его со всеми. Для работы нам понадобятся два счётчика, первый обходит все элементы по порядку, второй обходит все элементы и сравнивает их с текущим.
size_t i, j;
Сразу обратите внимание, что переменные всегда неотрицательные. Это приведёт к некоторым особенностям.
Теперь, если мы изменяем массив и оставляем в нём только разные элементы, то его размер поменяется (под размером мы здесь понимаем число различных элементов, фактический размер мы менять не станем), поэтому начальный размер массива передаётся через указатель. Этот же указатель будет хранить число элементов после преобразования.
Суть алгоритма: мы берём элемент и смотрим, были ли ДО него такие же элементы. Если нет, то копируем этот элемент, если были, то переходим к следующему элементу. Для того, чтобы копировать, введём счётчик pos – число уже найденных разных элементов массива.
size_t pos = 0;
и флаг unique, сигнализирующий о том, что текущий элемент не совпадает ни с одним их уже присутствующих в массиве.
int unique;
Сам цикл проверки
for (i = 0; i < size; i++) {
unique = 1;
//Чтобы не было перехода через 0 для j, идём до j > 0, но
//используем a[j-1], чтобы захватить нулевой элемент
for (j = i; j > 0; j--) {
if (EQ(a[i], a[j-1])) {
unique = 0;
break;
}
}
if (unique) {
a[pos++] = a[i];
}
}
Весь код
void quadDiff(T *a, size_t *out_size) {
size_t i, j;
size_t size = *out_size;
size_t pos = 0;
int unique;
for (i = 0; i < size; i++) {
unique = 1;
for (j = i; j > 0; j--) {
if (EQ(a[i], a[j-1])) {
unique = 0;
break;
}
}
if (unique) {
a[pos++] = a[i];
}
}
*out_size = pos;
}
Для цикла в цикле сложность будет порядка n2. Этот алгоритм сохраняет порядок элементов. Для массивов небольшого размера этот алгоритм будет быстрее других, ввиду простоты.
Существуют и более быстрые алгоритмы. Если взять отсортированный массив, то в нём одинаковые элементы стоят друг рядом с другом. Можно взять переменную prev, которая хранит предыдущее значение элемента массива. Если текущий элемент равен prev, то пропускаем его, если же нет, то копируем и меняем значение prev на значение текущего элемента.
Так как мы будем использовать стандартную быструю сортировку, то нам понадобятся также размер одного элемента и функция сравнения элементов.
void sortDiff(T *a, size_t item_size, size_t *out_size, int (*cmp)(const void *, const void *)) {
size_t i;
T prev = a[0];
size_t pos = 0;
qsort(a, *out_size, item_size, cmp);
for (i = 0; i < *out_size; i++) {
if (EQ(prev, a[i])) {
continue;
}
prev = a[i];
a[pos++] = a[i];
}
*out_size = pos;
}
Алгоритм тратит в среднем n∙log(n) на сортировку + один проход по массиву (ещё n), то есть сложность порядка n + n∙log(n). Однако нужно помнить, что быстрая сортировка для массивов небольшого размера неэффективна, поэтому для массивов небольшого размера этот алгоритм будет работать медленнее, чем квадратичный.
Методы, основанные на подсчёте
Если мощность множества элементов мала (мало разных элементов), то можно подсчитывать количество вхождений. Это особенно удобно, когда заранее известны все возможные элементы. Например, нужно найти все разные буквы в слове. Так как число различных символов (в нашем случае) не более 256, то можно создать массив из 256 элементов, равных нулю.
static int letters[256];
Используем численный код символа как индекс массива и увеличиваем значение соответствующего элемента.
void distinctLetters(char *str, int *out_size) {
const char *p = str;
int pos = 1;
while (*p++) {
letters[*p]++;
if (letters[*p] > 1) {
continue;
} else {
str[pos++] = *p;
}
}
*out_size = pos;
}
Когда элементы множества не известны, обычно используют специализированную структуру данных, позволяющую быстро добавлять элементы и проверять на вхождение, например, словарь, хэшированный массив или ассоциативный хэшированный массив.
