0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
||||||
1 | ||||||
Удалить повторяющиеся элементы в отсортированнном массиве02.08.2013, 11:48. Показов 2048. Ответов 12
Метки нет Все метки)
(
пример такого массива I[]={0,1,3,3,3,5,6,8,10,10}
Т.е. я так понимаю, нужно сдигать все элементы при повторении влево, и записывать в инт количество таких сдвижек, что бы передать массив в буферный и освободить лишнюю память. Что то туплю, и не могу понять как это "дешевле" сделать...На ум приходит только цикл в цикле.... может подскажите? Добавлено через 16 минут Пройтись один раз по массиву, переопределив все кроме одного пвоторяющихся чисел скажем -MAX_DBL получить I[] ={0,1,-MAX_DBL,-MAX_DBL,3,5,6,8,-MAX_DBL,10} И записать в новый массив все кроме -MAX_DBL... Добавлено через 30 минут Ну т.е. как то так: У нас есть упорядоченный массив NewIn, Мы удаляем повторяющиеся элементы и записываем в NewInTemp
0
|
|
02.08.2013, 11:48 | |
Ответы с готовыми решениями:
12
Массив: Удалить все повторяющиеся элементы, оставив в массиве только один. Удалить повторяющиеся элементы в массиве Удалить повторяющиеся элементы в массиве Удалить повторяющиеся элементы в ступенчатом массиве |
32 / 32 / 3
Регистрация: 04.04.2010
Сообщений: 414
|
|
02.08.2013, 12:32 | 2 |
зачем, уж если использовать 2 массива, то можно скопировать не повторяющиеся элементы за один проход, типа как у тебя только if(NewIn[i] != NewIn[i+1]) Тогда копируй в другой массив. Не хота разбираться почему там у тебя (M-2). Но последний символ тебе нужно обработать уже не в цикле. Сравниваешь его с массивом без повторений и если его там нету, кладешь его туда...
А вообще нужно использовать std::vector, тогда не нужны никаких 2 массива, а просто при первом же проходе в цикле, удаляешь повторяющиеся элементы, типа std::vector<int> v; v.erase(v.begin() + i);
1
|
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
|
02.08.2013, 12:45 [ТС] | 3 |
Ошибка, M-1 должно быть.
v.erase - довольно дорогая операция, так везде пишут. Как я понимаю, фактически один вызов erase равносилен проходу по вектору и сдвигу на один элемент. А у меня erase будет вызываться в цикле. А на счет за один проход, я же не знаю размер того массива который должен получиться. Или брать его равным первоначальному массиву?
0
|
32 / 32 / 3
Регистрация: 04.04.2010
Сообщений: 414
|
|
02.08.2013, 12:52 | 4 |
динамический массив тогда
Добавлено через 4 минуты Или в тот же std:vector просто добавляй
0
|
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
|
02.08.2013, 12:54 [ТС] | 5 |
Ну например тот же вектор использовать.
А на счет erese - это лишь мое предположение..может его и лучше использовать. А еще есть вроде такая член функция как unique ... вроде как сдвигает все повторяющиеся элементы в конец контенера, но не уверен, что здесь ее использование оправдано...
0
|
32 / 32 / 3
Регистрация: 04.04.2010
Сообщений: 414
|
|
02.08.2013, 12:58 | 6 |
так erase и не придется использовать если вы считаете её дорогой, просто проходите по вашему массиву и неповторяющиеся элементы копируете в vector. Ему не нужно знать, сколько элементов вы в него положите.
0
|
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
|
02.08.2013, 13:04 [ТС] | 7 |
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||||||
02.08.2013, 13:47 | 8 | |||||
второй массив не нужен
0
|
32 / 32 / 3
Регистрация: 04.04.2010
Сообщений: 414
|
|
02.08.2013, 14:01 | 9 |
ya_noob, так утечка памяти же будет, когда мы в вектор копируем, мы можем потом удалить исходный массив, а тут у нас лишние элементы в массиве всегда будут хранится...
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
02.08.2013, 14:52 | 10 |
я показал оптимальный алгоритм, работающий за n операций и не требующий дополнительной памяти (ТС предлагал за 2n операций и n дополнительной памяти).
С утечкой памяти можно справиться следующим образом: вместо сишного массива создаем vector< int >, выполняем ф-цию del_rep(...) для вектора и затем вызываем erase(...) для оставшейся части вектора в конце (начальная позиция итератора вычисляется исходя из результата ф-ции del_rep(...)). элементарно. в итоге имеем увеличение кол-ва операций до 2n (как у ТС), но дополнительную память не использовали. Win.
0
|
32 / 32 / 3
Регистрация: 04.04.2010
Сообщений: 414
|
|
02.08.2013, 15:48 | 11 |
ya_noob, Да, так будет оптимальней, имхо
0
|
В астрале
![]() 8048 / 4805 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
02.08.2013, 15:50 | 12 |
ya_noob, Если использовать вектора, так использовать std::unique, а не самописные велосипеды
2
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
02.08.2013, 16:13 | 13 |
А если ТСу нужно понять как оно работает внутри?
Я нигде не писал, что мой подход к контролю памяти оптимален. просто вектор первым пришел на ум
0
|
02.08.2013, 16:13 | |
Помогаю со студенческими работами здесь
13
Сортировка Хоара: Найти повторяющиеся элементы в массиве А, которые присутствуют в массиве В Найти повторяющиеся элементы в массиве А, которые присутствуют в массиве В Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |