Учебная версия на русском. Код и его вывод сохранены в исходном виде.
Массивы в C: удаление повторяющихся элементов
Удалите повторы из отсортированного массива на C с помощью двух индексов. Сохраните уникальные значения в исходном массиве и выведите их количество.
Прочитайте N и массив из N целых чисел, отсортированных по неубыванию. Удалите повторяющиеся значения без второго массива. Оставьте по одному экземпляру каждого значения и выведите новую длину и уникальные элементы.
Используйте индексы чтения и записи. Если прочитанное значение отличается от последнего сохранённого, запишите его в arr[write] и увеличьте индекс записи. При N = 1 массив не меняется; если все значения равны, остаётся одно.
Ввод
Первая строка: N. Вторая строка: N целых чисел в порядке неубывания.
Вывод
Первая строка: число уникальных значений. Вторая строка: эти значения через пробел.
Ограничения
- 1 <= N <= 1000
- -1000 <= arr[i] <= 1000
- Входной массив отсортирован по неубыванию.
- Дополнительная память O(1).
Подсказки
- Сохраните первый элемент: N не меньше единицы.
- Сравнивайте с последним сохранённым значением.
Код C
#include <stdio.h>
#define MAX_N 1000
int remove_duplicates(int arr[], int n) {
// TODO: Compact unique values into arr[0..write-1] and return write.
(void)arr;
return n;
}
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
int arr[MAX_N];
for (int i = 0; i < n; ++i) {
if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
if (i > 0 && arr[i] < arr[i - 1]) return 1;
}
int length = remove_duplicates(arr, n);
printf("%d\n", length);
for (int i = 0; i < length; ++i) {
printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
}
return 0;
}Решение и объяснение
Начните с write = 1. Перебирайте элементы с read = 1; если arr[read] отличается от arr[write - 1], скопируйте его в arr[write] и увеличьте write.
Выведите write и префикс этой длины. Время работы O(N), дополнительная память O(1).
Код решения
#include <stdio.h>
#define MAX_N 1000
int remove_duplicates(int arr[], int n) {
int write = 1;
for (int read = 1; read < n; ++read) {
if (arr[read] != arr[write - 1]) {
arr[write] = arr[read];
++write;
}
}
return write;
}
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
int arr[MAX_N];
for (int i = 0; i < n; ++i) {
if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
if (i > 0 && arr[i] < arr[i - 1]) return 1;
}
int length = remove_duplicates(arr, n);
printf("%d\n", length);
for (int i = 0; i < length; ++i) {
printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
}
return 0;
}Частые вопросы
Почему код и вывод остаются на английском?
Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.