Видалення повторень з відсортованого масиву
Тема "Опрацювання одновимірних масивів" розділу "Алгоритми і програми"
Змагання > Масиви Видалення повторень з відсортованого масиву
Дано відсортований масив цілих чисел. Видаліть з нього елементи, що повторюються так, щоб кожне число в ньому зустрічалося тільки о один раз. Реалізуйте розв'язок за лінійний час.
Вхідні дані.Перший рядок містить кількість елементів n (1 ≤ n ≤ 100) масиву. Другий рядок містить n цілих чисел у відсортованому порядку, кожне число не перевищує 100 за модулем.
Вихідні дані. Вивести відсортований масив з видаленими елементами що повторюються.
Практикум програмування на eolymp.com з чатом ChatGPT
Один з можливих способів вирішення цієї задачі за лінійний час полягає в тому, щоб проходитися по масиву та зберігати лише унікальні елементи. Оскільки масив відсортований, то унікальні елементи будуть розташовані поруч один з одним.
У цьому коді ми спочатку зчитуємо значення n та елементи масиву arr зі стандартного вводу. Потім ми створюємо порожній масив unique_arr, в якому будемо зберігати лише унікальні елементи.
Далі ми проходимо через кожен елемент масиву arr. Якщо поточний елемент arr[i] є першим елементом масиву arr (тобто i == 0) або він відрізняється від попереднього елемента arr[i-1], то ми додаємо його до масиву unique_arr.
Нарешті, ми виводимо масив unique_arr за допомогою функції print(). Оператор * перед масивом unique_arr дозволяє розділити його елементи пробілами під час виведення.
Цей алгоритм має складність O(n), оскільки ми проходимо через кожен елемент масиву лише один раз.
