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

Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы - C++

Восстановить пароль Регистрация
 
Freemen_
0 / 0 / 0
Регистрация: 28.06.2014
Сообщений: 5
28.06.2014, 16:51     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #1
Вводится длина одномерного массива и значения его элементов. Удалить из исходного массива уникальные (не повторяющиеся) элементы. Результат вывести.
вот мой результат . только вот в чем проблема, числа не удаляются , а в выводе числа идут по порядку. Пожалуйста срочно нужна помощь
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
34
35
#include <iostream>
#include <conio.h>
int main()
{
int N;
cout << "Enter number of elements:" <<endl;
cin >> N;
int *mas1 = new int [ N ];
int *mas2 = new int [ N ];
 
cout << endl << "Input elements:" << endl;
for ( int i = 0; i < N; i++ )
cin >> mas1[i];
 
int k = 0;
bool flag;
 
for ( int i = 0; i < N; i++ )
{
flag = false;
for ( int j = i+1; j < N; j++)
if ( mas1[i] == mas1[j] )       flag = true;
if (!flag)
mas2[k++] = mas1[i];
}
cout << endl << "Output: " <<endl;
for (  int i = 0; i < k; i++ )
cout << mas2[i] << "\t";
delete [] mas1;
delete [] mas2;
 
getch();
 
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.06.2014, 16:51     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы
Посмотрите здесь:

C++ Удалить из массива повторяющиеся элементы
сформировать из исходного массива новый, разместив в нем элементы исходного массива, отсортированные по три C++
удалить из массива повторяющиеся элементы, оставив только их первые вхождения. класс-контейнер вектор C++
C++ Как удалить из исходного массива не повторяющиеся элементы?
C++ Удалить из массива все элементы, которые меньше среднеарифметического значения всех элементов исходного массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BatonPro
30 / 30 / 24
Регистрация: 21.06.2014
Сообщений: 81
28.06.2014, 19:16     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #2
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
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <conio.h>
#include <iostream>
using namespace std;
int main()
{
int N;
cout << "Enter number of elements:" <<endl;
cin >> N;
int *mas1 = new int [ N ];
 
 
cout << endl << "Input elements:" << endl;
for ( int i = 0; i < N; i++ )
cin >> mas1[i];
 
for(int j,i=0;i<N;i++)
{
    for(j=i+1;j<N;j++)
    {
        if(mas1[i]==mas1[j])
            break;
    }
    if(j==N)
    {
        for(j=i;j<N-1;j++)
        {
            mas1[j]=mas1[j+1];
        }
        i--;
        N--;
 
    }
}
 
 
cout << endl << "Output: " <<endl;
for (  int i = 0; i < N; i++ )
cout << mas1[i] << "\t";
delete [] mas1;
 
getch();
 
return 0;
}
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
28.06.2014, 19:30     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #3
O(n2) плохо.
На вскидку есть способ n*log(n)
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
28.06.2014, 19:43     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #4
это скорее всего задачка по практике по проге с универа, так что нормал!
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
28.06.2014, 20:25     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #5
Цитата Сообщение от Kukurudza Посмотреть сообщение
На вскидку есть способ n*log(n)
С сохранением оригинального порядка?
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
28.06.2014, 20:28     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #6
да(еще одын симвал)
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
28.06.2014, 20:41     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #7
Цитата Сообщение от Kukurudza Посмотреть сообщение
да(еще одын симвал)
) И какой?
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
28.06.2014, 20:47     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #8
Очевидно, что используя любую стабильную сортировку со сложностью n log n
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
28.06.2014, 20:56     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #9
Цитата Сообщение от Voivoid Посмотреть сообщение
Очевидно, что используя любую стабильную сортировку со сложностью n log n
Обратно то как порядок восстановить? янп
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
28.06.2014, 22:36     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #10
можно идти по массиву, кидать числа в сет, и не добавлять в результат, если оно уже есть в сете.

или если числа маленькие вообще можно за O(n) решить!
IrineK
Заблокирован
29.06.2014, 04:12     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #11
Цитата Сообщение от Freemen_ Посмотреть сообщение
Удалить из исходного массива
Цитата Сообщение от BatonPro Посмотреть сообщение
N--;
Это - не удаление.

Цитата Сообщение от SlavaSSU Посмотреть сообщение
можно идти по массиву, кидать числа в сет, и не добавлять в результат, если оно уже есть в сете.
Тогда там будут уникальные элементы и по одному не уникальному. Оно нам надо?

ИМХО, суть задачи в том, чтобы уметь ручками удалять элементы из динамического массива, преобразовывая его размерность.
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
29.06.2014, 05:22     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #12
можно добавить все элементы массива в std::unordered_multiset, а потом проходя по этому множеству выудить все элементы, для которых std::unordered_multiset::count вернула > 1
IrineK
Заблокирован
29.06.2014, 05:27     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #13
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//Удалить из исходного массива уникальные (не повторяющиеся) элементы
#include <iostream>
#include <iomanip>
 
//----------------------------------ручной ввод num в пределах lower < num < upper
template <typename T>
void SafeInput (T &num, T lower, T upper)
{
    while (!(std::cin >> num) || !(std::cin.peek() == '\n' || std::cin.peek() == '\t' || std::cin.peek() == ' ') 
                    && num > lower && num < upper)
    {
        std::cin.clear();
        while (std::cin.get() != '\n');
        std::cout << "Ошибка. Попробуйте снова\n";
    }
}
 
//----------------------------------ручной ввод num
template <typename T>
void SafeInput (T &num)
{
    while (!(std::cin >> num) || !(std::cin.peek() == '\n' || std::cin.peek() == '\t' || std::cin.peek() == ' '))
    {
        std::cin.clear();
        while (std::cin.get() != '\n');
        std::cout << "Ошибка. Попробуйте снова\n";
    }
}
 
//----------------------------------создаем массив с ручным вводом
double *CreateArray (int N)
{
    double *arr = new double [N];
    for (int i = 0; i<N; i++)
        SafeInput<double>(arr[i]);
 
    return arr;
}
 
//---------------------------------обертка для очистки памяти
void DeleteArray( double *arr)
{
    delete [] arr;
}
 
//----------------------------------смотрим на массив
void PrintArray (double *arr, int N)
{
    for (int i = 0; i<N; i++)
        std::cout << std::fixed << std::setw(7) << std::setprecision (3) << *(arr+i) << "\n";
}
 
//---------------------------------является ли уникальным элемент на позиции pos
bool IsUnique (double *arr, int N, int pos)
{
    if (pos < 0 || pos > N-1)
        return false;
 
    for (int i = 0; i<N; i++)
        if ( i != pos && *(arr+i) == *(arr+pos))
            return false;
 
    return true;
}
 
//---------------------------------удаляем элемент на позиции pos
bool Erase (double *arr, int &N, int pos)
{
    if (pos < 0 || pos > N-1)
        return false;
    
    if (N == 1)
    {
        DeleteArray (arr);
        arr = NULL;
        N = 0;
        return true;
    }
 
    double *temp = new double [N-1];
    int i = 0;
    for ( ; i<pos; i++)
        *(temp+i) = *(arr+i);
    for ( ; i<N-1; i++)
        *(temp+i) = *(arr+i+1);
 
    DeleteArray (arr);
    arr = NULL;
    arr = new double [N-1];
    for (i = 0 ; i<N-1; i++)
        *(arr+i) = *(temp+i);
    N--;
    DeleteArray (temp);
 
    return true;
}
 
//--------------------------------собственно, задача
void Task (double *arr, int &N)
{
    for (int i = 0; i<N; i++)
        if (IsUnique(arr, N, i))
        {   
            Erase (arr, N, i);
            i--;
        }
}
 
//----------------------------------------------------------------------------
int main()
{   
    setlocale (LC_CTYPE, "Russian");
 
    int N;
    std::cout << "Размерность массива N = ";
    SafeInput<int> (N, 0, 21); // 0 < N < 21
 
    std::cout << "Введите массив:\n";
    double *arr = CreateArray (N);
    std::cout << "Массив:\n";
    PrintArray (arr, N);
 
    Task(arr,N);
    std::cout << "\nПосле удаления уникальных элементов:\n";
    PrintArray (arr, N);
 
    if (N)
        DeleteArray(arr);
    
    std::cin.sync();    
    std::cin.get();
    return 0;
}
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
29.06.2014, 05:39     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #14
У меня до сих пор вопрос: как выделить все повторяющиеся элементы, сохранив при этом их порядок, за O(n*log(n))?
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
29.06.2014, 06:15     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #15
gray_fox.
1. за каждым элементом в массиве закрепляем его порядковый номер O(n)
2. сортируем по величине элементу O(n * log(n))
3. проходим по отсортированному массиву и удаляем элемент, если его соседи ему не равны O(n)
4. заново сортируем по порядковому номеру O(n * log(n))
Итого: O(n) + O(n * log(n)) + O(n) + O(n * log(n)) = 2 * O(n * log(n)) = O(n * log(n))
gray_fox
29.06.2014, 06:25
  #16

Не по теме:

Kukurudza, Иа и диод)

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.06.2014, 13:20     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы
Еще ссылки по теме:

C++ Массив: Удалить все повторяющиеся элементы, оставив в массиве только один.
Массив: Получить массив, который содержит все элементы исходного массива, кратные трем C++
Удалить из массива повторяющиеся элементы, оставив только их первые вхождения C++

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

Или воспользуйтесь поиском по форуму:
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
29.06.2014, 13:20     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы #17
IrineK, ой да, а вчера понял задачу как "удалить из массива элементы так, чтобы каждый остался в 1 экземпляре"...

ну тогда наоборот кидать в результат, если оно уже есть, и в конце еще по одному экземпляру добавить.
Yandex
Объявления
29.06.2014, 13:20     Массив. Удалить из исходного массива уникальные (не повторяющиеся) элементы
Ответ Создать тему
Опции темы

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