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
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++;
    }
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.08.2013, 11:48
Ответы с готовыми решениями:

Массив: Удалить все повторяющиеся элементы, оставив в массиве только один.
Помогите, народ! Срочно нужна программа. Собственно задание: В целочисленном массиве k(n),...

Удалить повторяющиеся элементы в массиве
Есть массив array(11) { =&gt; string(22) &quot;Программист&quot; =&gt; string(22) &quot;Программист&quot; ...

Удалить повторяющиеся элементы в массиве
Имеем массив строк: 123 123 123 9 9 9 9 qw

Удалить повторяющиеся элементы в ступенчатом массиве
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data;...

12
32 / 32 / 3
Регистрация: 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);
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
Цитата Сообщение от Maxak Посмотреть сообщение
А на счет за один проход, я же не знаю размер того массива который должен получиться.
динамический массив тогда

Добавлено через 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
Цитата Сообщение от Maxak Посмотреть сообщение
А на счет erese - это лишь мое предположение..может его и лучше использовать.
так erase и не придется использовать если вы считаете её дорогой, просто проходите по вашему массиву и неповторяющиеся элементы копируете в vector. Ему не нужно знать, сколько элементов вы в него положите.
0
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
02.08.2013, 13:04  [ТС] 7
Цитата Сообщение от gore-lykovoe Посмотреть сообщение
так erase и не придется использовать если вы считаете её дорогой, просто проходите по вашему массиву и неповторяющиеся элементы копируете в vector. Ему не нужно знать, сколько элементов вы в него положите.
Ну это я понял.
Я к том, что может и вариант с erase то же рабочий=)
0
_
317 / 151 / 27
Регистрация: 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;
}
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
Цитата Сообщение от gore-lykovoe Посмотреть сообщение
так утечка памяти же будет
я показал оптимальный алгоритм, работающий за 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
Цитата Сообщение от ForEveR Посмотреть сообщение
Если использовать вектора, так использовать std::unique, а не самописные велосипеды
А если ТСу нужно понять как оно работает внутри?
Я нигде не писал, что мой подход к контролю памяти оптимален. просто вектор первым пришел на ум
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.08.2013, 16:13
Помогаю со студенческими работами здесь

Как удалить повторяющиеся элементы в массиве?
Как удалить повторяющиеся элементы в массиве? Добавлено через 49 минут я знаю что нужно сначала...

Удалить все повторяющиеся элементы в массиве
Удалить все повторяющиеся элементы, оставив только их первые вхождения, то есть получить массив...

Сортировка Хоара: Найти повторяющиеся элементы в массиве А, которые присутствуют в массиве В
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;time.h&gt; int comp(const void * a, const void...

Найти повторяющиеся элементы в массиве А, которые присутствуют в массиве В
Повторяющиеся элементы в массиве А, которые присутствуют в массиве В


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru