Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
Студент
121 / 132 / 39
Регистрация: 07.04.2011
Сообщений: 503
1

Создать третий массив, в котором нужно собрать общие элементы двух массивов

18.08.2013, 23:26. Показов 1469. Ответов 8
Метки нет (Все метки)

Элементы, которые есть только в массиве А или только в массиве В, заполнить ими массив C.
Всё работает, но громоздко както, реально за O(n2)?
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
int main(size_t argc, char * argv[])
{
 
    //3.    Элементы, которые есть только в массиве А или только в массиве В.
    
    int A[] = {34,35,36,37,38,53,54,55},
            B[] = {34,35,54,2,4,6},
            C[20];
 
    size_t i = 0,
                 j = 0,
                 k = 0,
                 len_a = sizeof A / sizeof (int),
                 len_b = sizeof B / sizeof (int);           
 
    unsigned char flag = 0;
    
    for( i = 0; i < len_a; i++ ) //Ищем который есть только в массиве А
    {
        for( j = 0; j < len_b; j++ ) 
        {
            if( A[i] == B[j] ) {
                flag = 1;
            }
        }
        if(flag == 0) {
                C[k++] = A[i];
        }
        flag = 0;
    }
    
    for( i = 0; i < len_b; i++ ) //Ищем который есть только в массиве B
    {
        for( j = 0; j < len_a; j++ )
        {
            if( B[i] == A[j] ) {
                flag = 1;
            }
        }
        
        if(flag == 0) {
                C[k++] = B[i];
        }
        flag = 0;
    }
    
    for( i = 0; i < k; i++ )
    {
        printf("%d\n", C[i]);
    }
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.08.2013, 23:26
Ответы с готовыми решениями:

Создать третий массив, в котором нужно собрать общие элементы двух массивов
Даны два массива: A и B. Необходимо создать третий массив, в котором нужно собрать общие элементы...

Создать третий массив, в котором нужно собрать элементы двух заданных массивов
Даны два массива : А и B. Необходимо создать третий массив, в котором нужно собрать: Элементы...

Создать массив минимально возможного размера, в котором нужно собрать общие элементы двух заданных массивов
Даны два массива: А и B (M и N вводятся с клавиатуры). Необходимо создать третий массив...

Создать третий массив минимально возможного размера, в котором нужно собрать элементы обоих массивов
Даны два массива: А и B (M и N вводятся с клавиатуры). Необходимо создать третий массив минимально...

8
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
19.08.2013, 00:07 2
Это по-твоему не https://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{2}) ? Если небольшие элементы только могут быть в интервале [a;b] последовательных целых чисел, то можно сделать за O(b-a+1)
1
81 / 81 / 33
Регистрация: 03.03.2013
Сообщений: 311
19.08.2013, 10:19 3
А что такое О() ?
0
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16828 / 6706 / 880
Регистрация: 12.06.2012
Сообщений: 19,967
19.08.2013, 23:00 4
Novi4ekC, http://ru.wikipedia.org/wiki/%... 0.BA.D0.B8 -> http://ru.wikipedia.org/wiki/%... 1%82%D1%8C
1
17 / 17 / 6
Регистрация: 02.07.2011
Сообщений: 67
25.08.2013, 19:12 5
Создать области памяти M1 и M2, размером по 232бит (512Мб) каждая, заполненные нулями.
Для каждого элемента первого массива установить соответствующий бит M1 в true. Например, для A[i]==30 установить 30-й бит M1 в true.
Для второго массива проделать то же самое с M2.
Почленно применить операцию xor для M1 и M2. Когда результат равен 1, добавлять новый элемент в третий массив.

Не знаю, можно ли встретить такое на практике. Но сложность https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(n\right).

Dani, https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(b-a+1\right) разве не сокращается до https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(1\right)?
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
25.08.2013, 20:48 6
andreysv, не сокращается, т.к. зависит от параметров (a, b, которые не константные).

Добавлено через 3 минуты
O(1) - это линейный алгоритм, а тут есть циклы. n = b-a+1, O(2*n) = O(n)
0
17 / 17 / 6
Регистрация: 02.07.2011
Сообщений: 67
25.08.2013, 21:26 7
Если n = b-a+1, то O(n) - поведение алгоритма в зависимости от диапазона допустимых значений элементов массива.
А рассматривается зависимость от размера массивов. Поэтому считаю, что корректней было бы O((b-a+1)*n).
Где n - кол-во элементов в массиве.
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
25.08.2013, 23:41 8
andreysv, откуда квадратичная сложность берется при заполнении массива появлений чисел и его обработке? Пусть возможные числа принадлежат интервалу [x; y]. Заводим массив F[x; y] или F[0; y-x]. Заполняем числа из массива A: это сделаем за длину массива A. Затем смотрим массив B - за длину массива B. Если F[ B[i] ] == 0 то число B[i] только в массиве B и увеличиваем F[B[i]] на единицу. Затем снова смотрим массив A - за длину массива A. Если F[ A[i] ] == 0, то число A[i] только в массиве A. Итого: Длина_массива_А + Длина_массива_В + Длина_массива_А = O(3*n) = O(n)
1
17 / 17 / 6
Регистрация: 02.07.2011
Сообщений: 67
26.08.2013, 01:23 9
Dani, согласен. Только квадратичной сложности нет, т.к. границы диапазона [a; b] известны и константны (забыл указать в предыдущем комментарии): https://www.cyberforum.ru/cgi-bin/latex.cgi?[\frac{-2^{32}}{2};\frac{2^{32}}{2}-1]. Отсюда O((b-a+1)*n) = O(n). Считаю, что сложность будет O(n2), если одновременно меняются b и n.

Добавлено через 40 минут
А, ну, да. Сложность будет O(n). Умножения здесь точно нет.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.08.2013, 01:23

Создать третий массив минимально возможного размера, в котором нужно собрать элементы обоих массивов
Вот Задача Даны два массива: А и B (M и N вводятся с клавиатуры). Необходимо создать третий...

Создать третий массив минимально возможного размера, в котором нужно собрать элементы обоих массивов
2. Даны два массива: А и B (M и N вводятся с клавиатуры). Необходимо создать третий массив...

Создать массив, в котором нужно собрать элементы двух заданных массивов
Подскажите, пожалуйста, как решить следующую задачу с помощью ссылок и операторов new и delete ...

Создать третий массив, в котором собрать элементы двух предыдущих
Есть два одномерных динамических массива: А и B. Необходимо создать третий массив С, в котором надо...


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

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

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