Как проверить вхождение элемента в массив эффективным образом?

@fanfuntik · Регистрация: 08.09.2018

Студворк — интернет-сервис помощи студентам

Встала задача:
Даны два массива, элементы которых упорядочены по возрастанию (и зачем это дали?). Найти количество уникальных элементов, то есть, которые входят в один массив, но не входят в другой.

Пример
a[5] = {1,2,3,4,5,6}
b[6] = {3,4,5,6,7,8,9}
результатом будет 5 (1,2,7,8,9)

Сначала решил через множества:
нашел разность a-b; b-a; затем объединил их и получил количество уникальных элементов.

но вроде не пахнет эффективным решением, да и без массивов.. не думаю, что зачтут такую задачу..

Помогите с идеями, как подойти к задаче?)

Спасибо всем большое.

@zss · 15.09.2018, 19:47

можно через map (и сортировать необязательно):

C++
1
2
3
4
5
6
7
8
9
10
11
a[5] = {1,2,3,4,5,6};
b[6] = {3,4,5,6,7,8,9};
map<int,int> m;
for(int i=0;i<5;i++)
  m[a[i]]++;
for(int i=0;i<6;i++)
  m[b[i]]++;
int count=0;
for(auto p=m.begin();p!=m.end();++p)
   if(p->second==1)
       count++;

@k0vpack · 15.09.2018, 20:20

fanfuntik,

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
int main()
{
    int A = 6, B = 8;
    int a[6] = {1,2,3,4,5,6}, b[8] = {3,4,5,6,7,8,9,10};
        int res = 0;
        for(int i = 0; i < A; i++)
        {
            bool isTrue = true;
            for(int j = 0; j < B; j++)
            {
                if(a[i] == b[j])
                {
                    isTrue = false;
                    break;
                }
            }
            if(isTrue)
            {
                res++;
            }
        }
 
         res += B - res - (B - A);
        cout << res;
        
 
    return 0;
}

A - размер первого массива, B - размер второго.

Croessmah · 15.09.2018, 20:34

Сообщение от fanfuntik

и зачем это дали?

Затем, что на сортированные множества можно натягивать более эффективные алгоритмы.

@fanfuntik · 19.09.2018, 16:08 **[ТС]**

Сообщение от Croessmah

Затем, что на сортированные множества можно натягивать более эффективные алгоритмы.

например? просто совсем не понимаю в эффективных алгоритмах. Как-то всю жизнь в лоб решал задачи.. Пытался сдать задачу используя множества, потом использовал словарь. Препод говорит, можно без этого обойтись ...

@sourcerer · 19.09.2018, 16:14

Сообщение от fanfuntik

например?

fanfuntik, например, библиотечные инструменты из заголовочных файлов algorithm, numeric и functional.

@RostikTawer · 19.09.2018, 16:20

Сообщение от fanfuntik

например?

к примеру, бинарный поиск элемента, на 1 триллиард т.е. 1 и 15 нулей, цикл пройдет 40 раз, т.е. для поиска элемента в любом случае будет нужно 40 прохождений цикла (только если элемент уникальный, в ином случае меньше), потому как любому другому поиску всегда нужно будет больше.

@DrOffset · 19.09.2018, 16:30

fanfuntik, можно биты использовать, как индикаторы того, есть ли число в массиве или нет. Затем просто сделать xor. Будет быстро.
Набросок:

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
#include <iostream>
#include <bitset>
 
int main()
{
    std::bitset<32> a;
    std::bitset<32> b;
 
    a[1] = 1;
    a[2] = 1;
    a[3] = 1;
    a[4] = 1;
    a[5] = 1;
    a[6] = 1;
 
    b[3] = 1;
    b[4] = 1;
    b[5] = 1;
    b[6] = 1;
    b[7] = 1;
    b[8] = 1;
    b[9] = 1;
 
    std::bitset<32> r = a ^ b;
 
    for(size_t i = 0; i < r.size(); ++i)
    {
        if(r[i]) std::cout << i << ' ';
    }
}

При желании, битсеты можно заменить обычными целыми.

Croessmah · 21.09.2018, 12:37

Сообщение от fanfuntik

например?

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
//g++  5.4.0
 
#include <iostream>
#include <list>
#include <iterator>
 
 
 
template<typename ForwardIterator>
ForwardIterator skip_equal(ForwardIterator first, ForwardIterator last)
{    
    if (first != last) {
        ForwardIterator prev = first++;
        while (first != last && *first == *prev) {
            ++prev;
            ++first;
        }
    }
    return first;
}
 
template<typename ForwardIterator, typename OutputIterator>
OutputIterator unique_difference(
    ForwardIterator f_begin, ForwardIterator f_end, 
    ForwardIterator s_begin, ForwardIterator s_end, 
    OutputIterator out)
{    
    while (f_begin != f_end && s_begin != s_end) {
        if (*f_begin < *s_begin) {
            *out = *f_begin;
            f_begin = skip_equal(f_begin, f_end);
        } else if (*s_begin < *f_begin) {
            *out = *s_begin;
            s_begin = skip_equal(s_begin, s_end);
        } else {
            f_begin = skip_equal(f_begin, f_end);
            s_begin = skip_equal(s_begin, s_end);
        }
    }
    while (f_begin != f_end) {
        *out = *f_begin;
        f_begin = skip_equal(f_begin, f_end);
    }
    while (s_begin != s_end) {
        *out = *s_begin;
        s_begin = skip_equal(s_begin, s_end);
    }
    return out;
}
 
int main()
{
    int first[] = {1, 2, 3, 4, 5, 6};
    int second[] = {3, 4, 5, 6, 7, 8, 9};
    
    unique_difference(
        std::begin(first), std::end(first), 
        std::begin(second), std::end(second), 
        std::ostream_iterator<int>(std::cout, " ")
    );
}

http://rextester.com/SBOBZ31541

Добавлено через 7 минут
fix:

C++
14
        while (first != last && !(*first < *prev) && !(*prev < *first )) {

@sourcerer · 23.09.2018, 08:28

Croessmah, не всегда работает, как ожидается. Например, с массивами

C++
1
2
int first[] = { 7, 1, 2, 3, 4, 5, 6 };
int second[] = { 3, 4, 5, 6, 7, 8, 9 };

вместо ожидаемого 1 2 8 9 получается такое:

Как проверить вхождение элемента в массив эффективным образом?

Использовал вариант твоего кода с исправлением:

Croessmah's unique_difference (2nd edition)

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
#include <iostream>
#include <iterator>
 
template <typename ForwardIterator>
ForwardIterator skip_equal(ForwardIterator first, ForwardIterator last)
{
    if (first != last)
    {
        auto prev = first++;
        while (first != last && !(*first < *prev) && !(*prev < *first))
        {
            ++prev;
            ++first;
        }
    }
    return first;
}
 
template <typename ForwardIterator, typename OutputIterator>
OutputIterator unique_difference(
    ForwardIterator f_begin, ForwardIterator f_end,
    ForwardIterator s_begin, ForwardIterator s_end,
    OutputIterator out)
{
    while (f_begin != f_end && s_begin != s_end)
    {
        if (*f_begin < *s_begin)
        {
            *out = *f_begin;
            f_begin = skip_equal(f_begin, f_end);
        }
        else if (*s_begin < *f_begin)
        {
            *out = *s_begin;
            s_begin = skip_equal(s_begin, s_end);
        }
        else
        {
            f_begin = skip_equal(f_begin, f_end);
            s_begin = skip_equal(s_begin, s_end);
        }
    }
    while (f_begin != f_end)
    {
        *out = *f_begin;
        f_begin = skip_equal(f_begin, f_end);
    }
    while (s_begin != s_end)
    {
        *out = *s_begin;
        s_begin = skip_equal(s_begin, s_end);
    }
    return out;
}
 
int main()
{
    int first[] = { 7, 1, 2, 3, 4, 5, 6 };
    int second[] = { 3, 4, 5, 6, 7, 8, 9 };
 
    unique_difference(std::begin(first), std::end(first), std::begin(second), std::end(second),
        std::ostream_iterator<int>(std::cout, " "));
}

@fanfuntik · 23.09.2018, 11:16 **[ТС]**

все нормально, в условии задачи даны упорядоченные массивы.

Добавлено через 32 секунды
спасибо большое за ваши идеи и подходы.

пробовал сделать, препод смотрит как на дурака, говорит, проще можно и без использования дополнительных сетов и прочее. два решения своих приносил (множества, банальный перебор), отсюда взял идею битсета - не принимает.
уже идей никаких не осталось.
кто-нибудь знает, эффективнее перебора и без использования библиотек что может быть?

если записать оба массива, и сделать бинарный поиск каждого элемента одного массива в другом (и наоборот элементы другого ищутся в первом) нормально будет? или слишком мудрено?

@sourcerer · 23.09.2018, 11:33

Сообщение от fanfuntik

все нормально, в условии задачи даны упорядоченные массивы.

Точно. Ну тогда всё норм.

@woldemas · 23.09.2018, 11:33

Сообщение от fanfuntik

если записать оба массива, и сделать бинарный поиск каждого элемента одного массива в другом (и наоборот элементы другого ищутся в первом) нормально будет?

Достаточно только концы массивов.

@sourcerer · 23.09.2018, 11:36

fanfuntik, а в одном массиве могут быть повторяющиеся элементы? Скажем, вот такой вариант может быть?

C++
1
2
int first[] = { 1, 1, 2, 3, 4, 5, 6 };
int second[] = { 3, 4, 5, 6, 7, 8, 9 };

ValeryS · 23.09.2018, 11:38

Сообщение от fanfuntik

Даны два массива, элементы которых упорядочены по возрастанию (и зачем это дали?).

вот по моему это главное
пересечение начинается по первому элементу второго массива и заканчивается по последнему элементу первого массива

@sourcerer · 23.09.2018, 12:35

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
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstddef>
 
int main ()
{
    int first[] = { 1, 2, 3, 4, 5, 6 };
    int second[] = { 3, 4, 5, 6, 7, 8, 9 };
    int result[std::size(first) + std::size(second)];
 
    auto middle = std::copy (std::begin(first), std::end(first), std::begin(result));
    std::copy(std::begin(second), std::end(second), middle);
    std::inplace_merge(std::begin(result), middle, std::end(result));
 
    std::size_t numberOfUniqueElements = 1;
    for (std::size_t i = 0; i < std::size(result) - 1; ++i)
    {
        if (result[i] != result[i+1])
            ++numberOfUniqueElements;
        else
            --numberOfUniqueElements;
    }
 
    std::cout << "The number of unique elements: " << numberOfUniqueElements;
}

Croessmah · 23.09.2018, 12:56

Ну, можно еще мой код от шаблона избавить:

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
int main()
{
    size_t const N1 = 6;
    size_t const N2 = 7;
    int first[N1] = {1, 2, 3, 4, 5, 6};
    int second[N2] = {3, 4, 5, 6, 7, 8, 9};
    int result[N1 + N2];
    size_t result_size = 0;
    
    size_t i = 0;
    size_t j = 0;
    while (i != N1 && j != N2) {        
        if (first[i] < second[j]) {
            result[result_size++] = first[i];
            for (++i; i != N1 && first[i] == first[i - 1]; ++i); 
        } else if (second[j] < first[i]) {
            result[result_size++] = second[j];
            for (++j; j != N2 && second[j] == second[j - 1]; ++j); 
        } else {
            for (++i; i != N1 && first[i] == first[i - 1]; ++i);
            for (++j; j != N2 && second[j] == second[j - 1]; ++j);
        }
    }
    while (i != N1) {
        result[result_size++] = first[i];
        for (++i; i != N1 && first[i] == first[i - 1]; ++i); 
    }
    while (j != N2) {
        result[result_size++] = second[j];
        for (++j; j != N2 && second[j] == second[j - 1]; ++j);
    }
    
    for (size_t x = 0; x < result_size; ++x) {
        std::cout << result[x] << ' ';
    }
}

Добавлено через 3 минуты
fanfuntik, а нужно найти только количество?

А я то тут... найти количество можно и проще. )))

@sourcerer · 23.09.2018, 12:59

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstddef>
 
int main ()
{
    int first[] = { 1, 2, 3, 4, 5, 6 };
    int second[] = { 3, 4, 5, 6, 7, 8, 9 };
 
    std::size_t numberOfUniqueElements = 0;
 
    for (const auto elem : first)
        if (std::find(std::begin(second), std::end(second), elem) == std::end(second))
            ++numberOfUniqueElements;
 
    for (const auto elem : second)
        if (std::find(std::begin(first), std::end(first), elem) == std::end(first))
            ++numberOfUniqueElements;
 
    std::cout << "The number of unique elements: " << numberOfUniqueElements;
}

@stu4ent · 23.09.2018, 18:31

Сообщение от Croessmah

например?

Зачем такую хрень городить? Если можно написать эту функцию в несколько раз короче:

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
#include <iostream>
#include <vector>
#include <algorithm>
 
std::vector<int>
unique_difference(int* a, size_t size_a, int* b, size_t size_b) {
    std::vector<int> result;
    
    for (int i = 0; i < size_a; i++) {
        if ((a[i] < b[0]) or (a[i] > b[size_b - 1])
                or (std::find(b, b + size_b, a[i]) == (b + size_b))) {
            result.push_back(a[i]);
        }
    }
    
    return result;
}
 
int main() {
    int a[] = {1,2,3,4,5,6};
    int b[] = {3,4,5,6,7,8,9};
    
    auto diff = unique_difference(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int));
    for (auto v : diff) {
        std::cout << "unique: " << v << std::endl;
    }
            
    return 0;
}

или, если нужно только число элементов, то можно и так:

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
#include <iostream>
#include <algorithm>
 
int
count_unique_elements(int* a, size_t size_a, int* b, size_t size_b) {
    int counter = 0;
    
    for (int i = 0; i < size_a; i++) {
        if ((a[i] < b[0]) or (a[i] > b[size_b - 1])
                or (std::find(b, b + size_b, a[i]) == (b + size_b))) {
            counter++;
        }
    }
    
    return counter;
}
 
int main() {
    int a[] = {1,2,3,4,5,6};
    int b[] = {3,4,5,6,7,8,9};
    
    std::cout << count_unique_elements(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int)) << std::endl;
            
    return 0;
}

Croessmah · 23.09.2018, 19:39

Сообщение от stu4ent

Зачем такую хрень городить?

Ваш код вообще не выполняет поставленную задачу.

Смотрим что должно получиться при таких входных данных: 5 (1,2,7,8,9)
Смотрим что выдает Ваш код: http://rextester.com/SXUN6159

unique: 1
unique: 2

то есть Ваш код только из первой последовательности выбирает элементы, а нужно выбрать из обеих.

Моя хрень делает это за линейное время.

Новые блоги и статьи Все статьи Все блоги /
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .

@fanfuntik 1 / 0 / 1 Регистрация: 08.09.2018 Сообщений: 46

	Как проверить вхождение элемента в массив эффективным образом? 15.09.2018, 18:58. Показов 16464. Ответов 55 Метки нет (Все метки) Встала задача: Даны два массива, элементы которых упорядочены по возрастанию (и зачем это дали?). Найти количество уникальных элементов, то есть, которые входят в один массив, но не входят в другой. Пример a[5] = {1,2,3,4,5,6} b[6] = {3,4,5,6,7,8,9} результатом будет 5 (1,2,7,8,9) Сначала решил через множества: нашел разность a-b; b-a; затем объединил их и получил количество уникальных элементов. но вроде не пахнет эффективным решением, да и без массивов.. не думаю, что зачтут такую задачу.. Помогите с идеями, как подойти к задаче?) Спасибо всем большое. 0

@fanfuntik 1 / 0 / 1 Регистрация: 08.09.2018 Сообщений: 46
	23.09.2018, 11:16 [ТС]
	все нормально, в условии задачи даны упорядоченные массивы. Добавлено через 32 секунды спасибо большое за ваши идеи и подходы. пробовал сделать, препод смотрит как на дурака, говорит, проще можно и без использования дополнительных сетов и прочее. два решения своих приносил (множества, банальный перебор), отсюда взял идею битсета - не принимает. уже идей никаких не осталось. кто-нибудь знает, эффективнее перебора и без использования библиотек что может быть? если записать оба массива, и сделать бинарный поиск каждого элемента одного массива в другом (и наоборот элементы другого ищутся в первом) нормально будет? или слишком мудрено? 0