Вибірка унікальних елементів масиву
З Адачі - необхідно з невпорядкованого масиву елементів вибрати все унікальні елементи. Ускладнити задачу в такий спосіб - спробуємо не використовувати додаткової пам'яті, а унікальні елементи класти в поточний масив.
Найпростіший алгоритм: брати елемент і порівнювати його з усіма. Для роботи нам знадобляться два лічильника, перший обходить всі елементи по порядку, другий обходить всі елементи і порівнює їх з поточним.
Відразу зверніть увагу, що змінні завжди невід'ємні. Це призведе до деяких особливостей.
Тепер, якщо ми змінюємо масив і залишаємо в ньому тільки різні елементи, то його розмір зміниться (під розміром ми тут розуміємо число різних елементів, фактичний розмір ми міняти не будемо), тому початковий розмір масиву передається через покажчик. Цей же покажчик буде зберігати число елементів після перетворення.
Суть алгоритму: ми беремо елемент і дивимося, чи були ДО нього такі ж елементи. Якщо немає, то копіюємо цей елемент, якщо були, то переходимо до наступного елементу. Для того, щоб копіювати, введемо лічильник pos - число вже знайдених різних елементів масиву.
і прапор unique, що сигналізує про те, що поточний елемент не збігається ні з одним їх уже присутніх в масиві.
Сам цикл перевірки
Для циклу в циклі складність буде порядку n 2. Цей алгоритм зберігає порядок елементів. Для масивів невеликого розміру цей алгоритм буде швидше інших, зважаючи на простоту.
Існують і більш швидкі алгоритми. Якщо взяти відсортований масив, то в ньому однакові елементи стоять поруч один з одним. Можна взяти змінну prev, яка зберігає попереднє значення елемента масиву. Якщо поточний елемент дорівнює prev, то пропускаємо його, якщо ж ні, то копіюємо і міняємо значення prev на значення поточного елемента.
Так як ми будемо використовувати стандартну швидку сортування, то нам знадобляться також розмір одного елемента і функція порівняння елементів.
Алгоритм витрачає в середньому n ∙ log (n) на сортування + один прохід по масиву (ще n), тобто складність порядку n + n ∙ log (n). Однак потрібно пам'ятати, що швидке сортування для масивів невеликого розміру неефективна, тому для масивів невеликого розміру цей алгоритм буде працювати повільніше, ніж квадратичний.
Методи, засновані на підрахунку
Е слі потужність безлічі елементів мала (мало різних елементів), то можна підраховувати кількість входжень. Це особливо зручно, коли заздалегідь відомі всі можливі елементи. Наприклад, потрібно знайти всі різні літери в слові. Так як число різних символів (в нашому випадку) не більше 256, то можна створити масив з 256 елементів, рівних нулю.
Використовуємо чисельний код символу як індекс масиву і збільшуємо значення відповідного елемента.
Коли елементи множини не відомі, зазвичай використовують спеціалізовану структуру даних, що дозволяє швидко додавати елементи і перевіряти на входження, наприклад, словник. хешірованного масив або асоціативний хешірованного масив.
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 [email protected] Stepan Sypachev students