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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Yakov112
0 / 0 / 0
Регистрация: 08.12.2011
Сообщений: 69
#1

Функция: поиск неповторяющихся элементов массива - C++

20.10.2012, 23:42. Просмотров 1883. Ответов 8
Метки нет (Все метки)

помогите написать функцию по поиску количества не повторяющихся элементов в одномерном массиве
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2012, 23:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция: поиск неповторяющихся элементов массива (C++):

Поиск неповторяющихся элементов в массиве - C++
Подскажите пожалуйста более умный алгоритм для поиска разных элементов в трёх массивах A,B,C. for(int i(0);i<N;i++){ for(int...

Найти количество неповторяющихся элементов массива - C++
Помогите пожалуйста найти алгоритм, или код реализующий следующее: Имеется массив из n элементов(n вводится с клавиатуры), элементы...

Массив из неповторяющихся элементов исходного массива - C++
Рандомно задается массив. Необходимо составить массив из неповторяющихся элементов исходного массива, сохраняя порядок их следования....

Найти минимальный из неповторяющихся элементов двумерного массива - C++
Найти минимальный из неповторяющихся элементов двумерного массива.

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

Сформировать массив неповторяющихся элементов исходного массива - C++
Сформировать массив из неповторяющихся элементов исходного массива. Например : Из массива A = {2,5,2,6,8,5,1,9,4,3 } нужно получить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
John Prick
779 / 712 / 131
Регистрация: 27.07.2012
Сообщений: 2,045
Завершенные тесты: 3
21.10.2012, 00:16 #2
std::unique
Можно глянуть реализацию этой функции.
Yakov112
0 / 0 / 0
Регистрация: 08.12.2011
Сообщений: 69
21.10.2012, 00:41  [ТС] #3
John Prick, если бы она получилась, а то ерунду какую то выдает((((

Добавлено через 4 минуты
John Prick, вот код проги с условием задачи
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
/*
 
условие задачи:
Даны натуральное n и целые a1, a2, ..., an. Внутри последовательности могут быть 
повторяющиеся члены. Найти сколько разных чисел входят в последовательность по 1 разу.
 
*/
#include<iostream>
#include<locale>
#define N 100
using namespace std;
 
void inMas1(int &n, int a[N])
{
    for (int i=0; i < n; ++i)
    {
        cout << "\na[" << i << "]=";
        cin >> a[i];
    }
}
 
void uslov(int n, int a[N])
{   
    int k=0;
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
        {
            if( a[i]==a[j])
            k++;
        }
    cout<<n-k<<endl;
}
 
int main()
{
    setlocale(LC_ALL,"Rus");
    int n,i, a[N],k;
    cout<<"Введите n, n=";
    cin>>n;
    if(n==0)
    {
        cout<<"\nНекорректное n (n<1)";
        return 0;
    }
    inMas1(n,a);
    uslov(n,a);
    
 
    return 0;
}
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.10.2012, 02:06 #4
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
#include<iostream>
#include<locale>
#define N 100
using namespace std;
 
void inMas1(int &n, int a[N])
{
    for (int i=0; i < n; ++i)
    {
        cout << "\na[" << i << "]=";
        cin >> a[i];
    }
}
 
void uslov(int n, int a[N])
{   
    int k=0, t;
    for(int i=0; i<n; i++)
    {
        t=0;
        for(int j=0; j<n; j++)
        {
            if( a[i]==a[j])
            t++;
        }
        if(t==1)
            k++;
    }
    cout<<k<<endl;
}
 
int main()
{
    setlocale(LC_ALL,"Rus");
    int n,i, a[N],k;
    cout<<"Введите n, n=";
    cin>>n;
    if(n==0)
    {
        cout<<"\nНекорректное n (n<1)";
        return 0;
    }
    inMas1(n,a);
    uslov(n,a);
    
 
    return 0;
}
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
21.10.2012, 02:35 #5
Не знаю что за велосипеды тут написали, но алгоритм (Вы ведь вручную я так понимаю хотите написать) проще некуда: делаете функцию где сортируете содержимое своего массива (делаете его копию если важно чтобы он не менялся) после чего тупо идёте циклом по нему и считаете элементы которые не равны предыдущему элементу Могу написать в виде кода, но я думаю Вы и сами с этим справитесь так как это не сложно.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.10.2012, 03:04 #6
Цитата Сообщение от Gepar Посмотреть сообщение
после чего тупо идёте циклом по нему и считаете элементы которые не равны предыдущему элементу
тупо идти нельзя:
Вот отсортированный массив:
1 2 3 3
когда дойдете до первой тройки, то выведите ее на экран (ведь она не равна предыдущему)
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
21.10.2012, 03:09 #7
Gepar, нужно найти не количество разных элементов, а количество не повторяющихся
John Prick
779 / 712 / 131
Регистрация: 27.07.2012
Сообщений: 2,045
Завершенные тесты: 3
21.10.2012, 11:29 #8
Да, действительно, unique делает не совсем то: он оставляет только 1 элемент из группы повторяющихся. Чтобы подсчитать количество неповторяющихся надо в отсортированном массиве следить, чтобы ни предыдущий, ни следующий не равнялся текущему. Для крайних элементов, естественно, только один соседний проверяется.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.10.2012, 12:09 #9
алгоритмы со сложностью O(n^2) для очень больших массив не очень подойдут. Если массив из целых чисел и диапазон разброса значений не очень велик (например, не более 100 000 000 элементов от min до max), то можно с линейной сложностью, то есть работать будет мгновенно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Search(int *a, int n)
{
   int min, max, i, m, *count;
   min = max = a[0];
   for(i = 1; i < n; i++)
      if (a[i] < min) min = a[i];
      else if(a[i] > max) max = a[i];
   m = max - min + 1;
   count = new int[m];
   if (count == NULL)
      return;
   for(i = 0; i < n; i++)
      ++count[a[i] - min];
   for(i = 0; i < m; i++)
      if (count[i] == 1)
         std::cout << (i + min) << " ";
   delete[] count;
}
по поводу сортировки от Gepar (сложностью O(n ln n)) тоже вариант, только надо проверять не пары, а тройки элементов: у текущего элемента левого и правого соседа, ну и с граничными случаями отдельно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.10.2012, 12:09
Привет! Вот еще темы с ответами:

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

Функция должна вычислять разницы между суммой положительных элементов массива и суммой модулей отрицательных элементов массива - C++
Разработать функцию ,обрабатывающую массив и вычисляющую две величины.Кроме того,разработать две функции,которые вычисляют те же самые...

Функция: подсчет числа отрицательных элементов массива, и суммы положительных элементов матрицы - C++
написать функцию подсчета отрицательных элементов одномерного массива А(6) и сумму положит-х эл-ов матрицы В(6x6)

Массив и функция (количество нечетных элементов массива, минимальный из элементов и его номер) - C++
Кто добр в душе и может помочь,очень прошу-не откажите девушке!!! Целочисленный массив из N элементов заполнить случайными значениями...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
21.10.2012, 12:09
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru