Форум программистов, компьютерный форум CyberForum.ru

Удалить повторяющиеся элементы в отсортированнном массиве - C++

Восстановить пароль Регистрация
 
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
02.08.2013, 11:48     Удалить повторяющиеся элементы в отсортированнном массиве #1
пример такого массива 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
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    
int NewM = M;
    double MAX_DBL = 666666666666666;
    for(int i=0; i<(M-2); i++)
    {       
        if(NewIn[i] == NewIn[i+1])
        {
            NewIn[i] = -MAX_DBL;
            NewM--; 
        }
    }
    
    double *NewInTemp = new double[NewM];
    int *NewOutTemp = new int[NewM];
 
    int j =0;
    NewInTemp[0] = NewIn[0];
    for(int i=0; i<NewM; i++)
    {                   
        while(NewIn[j]==-MAX_DBL)   j++;
        NewInTemp[i] = NewIn[j]; 
        j++;
    }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gore-lykovoe
 Аватар для gore-lykovoe
31 / 31 / 1
Регистрация: 04.04.2010
Сообщений: 414
02.08.2013, 12:32     Удалить повторяющиеся элементы в отсортированнном массиве #2
Цитата Сообщение от Maxak Посмотреть сообщение
Пройтись один раз по массиву, переопределив все кроме одного пвоторяющихся чисел скажем -MAX_DBL
получить I[] ={0,1,-MAX_DBL,-MAX_DBL,3,5,6,8,-MAX_DBL,10}
И записать в новый массив все кроме -MAX_DBL...
зачем, уж если использовать 2 массива, то можно скопировать не повторяющиеся элементы за один проход, типа как у тебя только if(NewIn[i] != NewIn[i+1]) Тогда копируй в другой массив. Не хота разбираться почему там у тебя (M-2). Но последний символ тебе нужно обработать уже не в цикле. Сравниваешь его с массивом без повторений и если его там нету, кладешь его туда...

А вообще нужно использовать std::vector, тогда не нужны никаких 2 массива, а просто при первом же проходе в цикле, удаляешь повторяющиеся элементы, типа std::vector<int> v; v.erase(v.begin() + i);
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
02.08.2013, 12:45  [ТС]     Удалить повторяющиеся элементы в отсортированнном массиве #3
Ошибка, M-1 должно быть.
v.erase - довольно дорогая операция, так везде пишут. Как я понимаю, фактически один вызов erase равносилен проходу по вектору и сдвигу на один элемент. А у меня erase будет вызываться в цикле.
А на счет за один проход, я же не знаю размер того массива который должен получиться. Или брать его равным первоначальному массиву?
gore-lykovoe
 Аватар для gore-lykovoe
31 / 31 / 1
Регистрация: 04.04.2010
Сообщений: 414
02.08.2013, 12:52     Удалить повторяющиеся элементы в отсортированнном массиве #4
Цитата Сообщение от Maxak Посмотреть сообщение
А на счет за один проход, я же не знаю размер того массива который должен получиться.
динамический массив тогда

Добавлено через 4 минуты
Или в тот же std:vector просто добавляй
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
02.08.2013, 12:54  [ТС]     Удалить повторяющиеся элементы в отсортированнном массиве #5
Ну например тот же вектор использовать.

А на счет erese - это лишь мое предположение..может его и лучше использовать.
А еще есть вроде такая член функция как unique ... вроде как сдвигает все повторяющиеся элементы в конец контенера, но не уверен, что здесь ее использование оправдано...
gore-lykovoe
 Аватар для gore-lykovoe
31 / 31 / 1
Регистрация: 04.04.2010
Сообщений: 414
02.08.2013, 12:58     Удалить повторяющиеся элементы в отсортированнном массиве #6
Цитата Сообщение от Maxak Посмотреть сообщение
А на счет erese - это лишь мое предположение..может его и лучше использовать.
так erase и не придется использовать если вы считаете её дорогой, просто проходите по вашему массиву и неповторяющиеся элементы копируете в vector. Ему не нужно знать, сколько элементов вы в него положите.
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
02.08.2013, 13:04  [ТС]     Удалить повторяющиеся элементы в отсортированнном массиве #7
Цитата Сообщение от gore-lykovoe Посмотреть сообщение
так erase и не придется использовать если вы считаете её дорогой, просто проходите по вашему массиву и неповторяющиеся элементы копируете в vector. Ему не нужно знать, сколько элементов вы в него положите.
Ну это я понял.
Я к том, что может и вариант с erase то же рабочий=)
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.08.2013, 13:47     Удалить повторяющиеся элементы в отсортированнном массиве #8
второй массив не нужен
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
 
int del_rep( int *a, int size )
{
    int i = 0;
 
    for ( int j = 1; j < size; ++j )
        if ( a[ j ] != a[ i ] )
            a[ ++i ] = a[ j ];
 
    return i + 1;
}
void print( int *a, int size )
{
    for ( int i = 0; i < size; ++i )
        cout << a[ i ] << ' ';
    cout << endl;
}
 
int main()
{
    int size = 10;
    int a[] = { 0, 1, 3, 3, 3, 5, 6, 8, 10, 10 };
 
    cout << "source: ";
    print( a, size );
    size = del_rep( a, size );
    cout << "result: ";
    print( a, size );
 
    return 0;
}
gore-lykovoe
 Аватар для gore-lykovoe
31 / 31 / 1
Регистрация: 04.04.2010
Сообщений: 414
02.08.2013, 14:01     Удалить повторяющиеся элементы в отсортированнном массиве #9
ya_noob, так утечка памяти же будет, когда мы в вектор копируем, мы можем потом удалить исходный массив, а тут у нас лишние элементы в массиве всегда будут хранится...
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.08.2013, 14:52     Удалить повторяющиеся элементы в отсортированнном массиве #10
Цитата Сообщение от gore-lykovoe Посмотреть сообщение
так утечка памяти же будет
я показал оптимальный алгоритм, работающий за n операций и не требующий дополнительной памяти (ТС предлагал за 2n операций и n дополнительной памяти).
С утечкой памяти можно справиться следующим образом:
вместо сишного массива создаем vector< int >, выполняем ф-цию del_rep(...) для вектора и затем вызываем erase(...) для оставшейся части вектора в конце (начальная позиция итератора вычисляется исходя из результата ф-ции del_rep(...)). элементарно. в итоге имеем увеличение кол-ва операций до 2n (как у ТС), но дополнительную память не использовали. Win.
gore-lykovoe
 Аватар для gore-lykovoe
31 / 31 / 1
Регистрация: 04.04.2010
Сообщений: 414
02.08.2013, 15:48     Удалить повторяющиеся элементы в отсортированнном массиве #11
ya_noob, Да, так будет оптимальней, имхо
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
02.08.2013, 15:50     Удалить повторяющиеся элементы в отсортированнном массиве #12
ya_noob, Если использовать вектора, так использовать std::unique, а не самописные велосипеды
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2013, 16:13     Удалить повторяющиеся элементы в отсортированнном массиве
Еще ссылки по теме:

C++ Удалить повторяющиеся символы в массиве
C++ Найти повторяющиеся в массиве элементы
C++ Удалить все повторяющиеся элементы в векторе

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.08.2013, 16:13     Удалить повторяющиеся элементы в отсортированнном массиве #13
Цитата Сообщение от ForEveR Посмотреть сообщение
Если использовать вектора, так использовать std::unique, а не самописные велосипеды
А если ТСу нужно понять как оно работает внутри?
Я нигде не писал, что мой подход к контролю памяти оптимален. просто вектор первым пришел на ум
Yandex
Объявления
02.08.2013, 16:13     Удалить повторяющиеся элементы в отсортированнном массиве
Ответ Создать тему
Опции темы

Текущее время: 02:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru