Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
MickeyBlueEyes
Студент
120 / 131 / 39
Регистрация: 07.04.2011
Сообщений: 503
1

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

18.08.2013, 23:26. Просмотров 814. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.08.2013, 23:26
Ответы с готовыми решениями:

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

Создать третий массив на основе двух заданных массивов по условию
Создать 2 динамических массива различной размерности, указанной пользователем. Далее создать третий...

Создать третий массив такого же размера каждый элемент которого равен сумме соответствующих элементов двух первых массивов
Даны два двумерных массива одинаковых размеров. а) Создать третий массив такого же размера каждый...

Из двух упорядоченных массивов составить третий упорядоченный массив
#include &lt;iostream&gt; #include &lt;stdlib.h&gt; #include &lt;stdio.h&gt; using namespace std; //...

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

8
Dani
1394 / 638 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
19.08.2013, 00:07 2
Это по-твоему не http://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{2}) ? Если небольшие элементы только могут быть в интервале [a;b] последовательных целых чисел, то можно сделать за O(b-a+1)
1
Novi4ekC
81 / 81 / 33
Регистрация: 03.03.2013
Сообщений: 311
19.08.2013, 10:19 3
А что такое О() ?
0
KOPOJI
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16767 / 6654 / 869
Регистрация: 12.06.2012
Сообщений: 19,902
Завершенные тесты: 1
19.08.2013, 23:00 4
Novi4ekC, http://ru.wikipedia.org/wiki/%C0%EB%...B2.D0.BA.D0.B8 -> http://ru.wikipedia.org/wiki/%D0%92%...81%D1%82%D1%8C
1
19.08.2013, 23:00
andreysv
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, добавлять новый элемент в третий массив.

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

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

Добавлено через 3 минуты
O(1) - это линейный алгоритм, а тут есть циклы. n = b-a+1, O(2*n) = O(n)
0
andreysv
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
Dani
1394 / 638 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
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
andreysv
17 / 17 / 6
Регистрация: 02.07.2011
Сообщений: 67
26.08.2013, 01:23 9
Dani, согласен. Только квадратичной сложности нет, т.к. границы диапазона [a; b] известны и константны (забыл указать в предыдущем комментарии): http://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
26.08.2013, 01:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2013, 01:23

Есть 2 одномерных массива, нужно все не общие элементы записать в 3 массив
Помогите решить, буду очень благодарен

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

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


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

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

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