When you feel like giving up, remember why you started.

01 | ?? 題目描述

給你兩個(gè)數(shù)組，請(qǐng)分別求出兩個(gè)數(shù)組的交集和并集

在數(shù)學(xué)中，我們可以通過(guò)交集和并集來(lái)描述兩個(gè)集合之間的關(guān)系。

• 交集（Intersection）：指的是兩個(gè)集合中共有的元素組成的集合。可以用符號(hào) ∩ 來(lái)表示。例如，對(duì)于集合 A = {1, 2, 3} 和集合 B = {2, 3, 4} 來(lái)說(shuō)，它們的交集就是 {2, 3}，因?yàn)檫@些元素同時(shí)存在于兩個(gè)集合中。

• 并集（Union）：指的是將兩個(gè)集合中所有的元素取并集組成一個(gè)新的集合?？梢杂梅?hào) ∪ 來(lái)表示。例如，對(duì)于集合 A = {1, 2, 3} 和集合 B = {2, 3, 4} 來(lái)說(shuō)，它們的并集就是 {1, 2, 3, 4}，因?yàn)樗藘蓚€(gè)集合中的所有元素，且去除了重復(fù)的元素。

換句話說(shuō)，交集是尋找兩個(gè)集合中相同的元素，而并集則是將兩個(gè)集合中所有的元素合并在一起。

02 | ?? 解題思路

上述數(shù)學(xué)概念同樣適用于數(shù)組。當(dāng)我們要找到兩個(gè)數(shù)組的交集時(shí)，我們需要找到它們共有的元素。而當(dāng)我們要找到兩個(gè)數(shù)組的并集時(shí)，我們需要將它們中所有的元素合并在一起，并去除重復(fù)的元素。

交集

具體解題思路如下：

1. 首先，定義兩個(gè)數(shù)組A和B，分別表示待求交集的數(shù)組。
2. 創(chuàng)建一個(gè)空的集合（set）或者哈希集合（unordered_set），用于存儲(chǔ)交集的結(jié)果。集合是一種數(shù)據(jù)結(jié)構(gòu)，它只會(huì)存儲(chǔ)不重復(fù)的元素。
3. 遍歷數(shù)組A中的每個(gè)元素，將其添加到集合中。
4. 遍歷數(shù)組B中的每個(gè)元素，判斷該元素是否存在于集合中。如果存在，則說(shuō)明它是交集的一個(gè)元素，將其添加到另一個(gè)集合（結(jié)果集合）中。
5. 最后，將結(jié)果集合中的元素轉(zhuǎn)存到數(shù)組中，得到最終的交集數(shù)組。

• 時(shí)間 && 空間復(fù)雜度

  • 時(shí)間復(fù)雜度：

    • 遍歷數(shù)組A，將元素添加到集合中：O(n)，其中n是數(shù)組A的大小。
    • 遍歷數(shù)組B，判斷元素是否存在于集合中，并將交集元素添加到結(jié)果集合中：O(m)，其中m是數(shù)組B的大小。

    所以，總體的時(shí)間復(fù)雜度為O(n + m)，我們可以將其簡(jiǎn)化為O(max(n, m))，其中max(n, m)表示兩個(gè)數(shù)組中較大的大小。

  • 空間復(fù)雜度：

    • 使用一個(gè)集合來(lái)存儲(chǔ)數(shù)組A中的元素：O(n)，其中n是數(shù)組A的大小。
    • 使用一個(gè)結(jié)果集合來(lái)存儲(chǔ)交集元素：最壞情況下，結(jié)果集合的大小為min(n, m)，其中n和m分別是數(shù)組A和數(shù)組B的大小。

    所以，總體的空間復(fù)雜度為O(n + min(n, m))，我們可以將其簡(jiǎn)化為O(max(n, m))，其中max(n, m)表示兩個(gè)數(shù)組中較大的大小。

并集

• 具體的解題流程：

  1. 首先，定義兩個(gè)數(shù)組A和B，分別表示待求并集的數(shù)組。
  2. 創(chuàng)建一個(gè)空的集合（set）或者哈希集合（unordered_set），用于存儲(chǔ)并集的結(jié)果。集合是一種數(shù)據(jù)結(jié)構(gòu)，它只會(huì)存儲(chǔ)不重復(fù)的元素。
  3. 遍歷數(shù)組A中的每個(gè)元素，將其添加到集合中。
  4. 遍歷數(shù)組B中的每個(gè)元素，判斷該元素是否存在于集合中。如果不存在，則說(shuō)明它是并集的一個(gè)元素，將其添加到集合中。
  5. 最后，將集合中的元素轉(zhuǎn)存到數(shù)組中，得到最終的并集數(shù)組。

• 時(shí)間 && 空間復(fù)雜度
  • 時(shí)間復(fù)雜度
    將數(shù)組A中的元素插入集合：O(n)，其中n是數(shù)組A的大小。
    遍歷數(shù)組B，并將元素插入集合：O(m)，其中m是數(shù)組B的大小。
    因此，總體的時(shí)間復(fù)雜度為O(n + m)，我們可以將其簡(jiǎn)化為O(max(n, m))，其中max(n, m)表示兩個(gè)數(shù)組中較大的大小
  • 空間復(fù)雜度
    創(chuàng)建一個(gè)集合來(lái)存儲(chǔ)并集的結(jié)果：O(n + min(n, m))，其中n和m分別是數(shù)組A和數(shù)組B的大小。 在最壞情況下，如果兩個(gè)數(shù)組沒(méi)有重復(fù)元素，集合的大小為n + m。
    創(chuàng)建一個(gè)數(shù)組來(lái)存儲(chǔ)集合中的元素：O(n + min(n, m))，與創(chuàng)建集合的過(guò)程相同。
    所以，總體的空間復(fù)雜度為O(n + min(n, m))，我們可以將其簡(jiǎn)化為O(max(n, m))，其中max(n, m)表示兩個(gè)數(shù)組中較大的大小
    因此，整個(gè)算法的

03 | ?? 代碼片段

交集

#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<int> intersection(std::vector<int>& A, std::vector<int>& B) {
    std::unordered_set<int> setA(A.begin(), A.end()); // 將數(shù)組A中的元素放入集合
    std::unordered_set<int> resultSet;
    
    for (int num : B) {
        if (setA.count(num) > 0) { // 判斷num是否存在于集合setA中
            resultSet.insert(num); // 將num添加到結(jié)果集合中
        }
    }
    
    std::vector<int> result(resultSet.begin(), resultSet.end()); // 將結(jié)果集合轉(zhuǎn)存到數(shù)組中
    return result;
}

int main() {
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> B = {4, 5, 6, 7, 8};
    
    std::vector<int> result = intersection(A, B);
    
    std::cout << "Intersection: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

并集

#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<int> unionSet(std::vector<int>& A, std::vector<int>& B) {
    std::unordered_set<int> resultSet(A.begin(), A.end()); // 將數(shù)組A中的元素放入集合

    for (int num : B) {
        resultSet.insert(num); // 將數(shù)組B中的元素添加到集合中
    }
    
    std::vector<int> result(resultSet.begin(), resultSet.end()); // 將集合轉(zhuǎn)存到數(shù)組中
    return result;
}

int main() {
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> B = {4, 5, 6, 7, 8};
    
    std::vector<int> result = unionSet(A, B);
    
    std::cout << "Union Set: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-504934.html

到了這里，關(guān)于【每日算法 && 數(shù)據(jù)結(jié)構(gòu)(C++)】—— 02 | 數(shù)組的并交集（解題思路、流程圖、代碼片段）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！