I want a program to find duplicated elements in 2 arrays without using 2 nested loop. I've tried 2 for loop but it takes too much time.

Here what I have done:

for(j = 0; j < n; j  ){
    for(i = 0; i < m; i  ){
        if(arr1[i] == arr2[j]){
            // function
        } else if(arr1[i] != arr2[j]) {
            // another function
        }
    }
}

CodePudding user response：

Build a hashset from elements from array1, then iterate over array2 to find duplicates.

CodePudding user response：

• using bool visited array for array1, then check duplicates in array2 [it depends on array elements limitation]
• using map or set C STL
• using Trie data structure (advanced technique)

CodePudding user response：

This solution will show you 3 methods and measure the time that they need.

1. Your approach, using a nested loop
2. Using std::set_intersection
3. Using std::unordered_set

There are of course more possible solutions.

Please see:

#include <iostream>
#include <iterator>
#include <random>
#include <chrono>
#include <algorithm>
#include <unordered_set>

constexpr size_t ArraySize1 = 100000u;
constexpr size_t ArraySize2 = 150000u;

int main() {

    int arr1[ArraySize1], arr2[ArraySize2];

    // ---------------------------------------------------------------
    // Create some random numbers and fill both arrays with it
    std::random_device rd;  
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<> distrib(1, 2000000000);

    for (int& i : arr1) i = distrib(gen);
    for (int& i : arr2) i = distrib(gen);

    // ---------------------------------------------------------------
    // Test algorithms

    // 1. Nested loops
    auto start = std::chrono::system_clock::now();

    // ---
    for (size_t k = 0; k < ArraySize1;   k)
        for (size_t i = 0; i < ArraySize2;   i)
            if (arr1[k] == arr2[i])
                std::cout << arr1[k] << '\n';
    // ---

    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "Time with nested loops: " << elapsed.count() << " ms\n\n";

    // 2. Set intersection
    start = std::chrono::system_clock::now();

    // ---
    std::sort(std::begin(arr1), std::end(arr1));
    std::sort(std::begin(arr2), std::end(arr2));
    std::set_intersection(std::begin(arr1), std::end(arr1), std::begin(arr2), std::end(arr2), std::ostream_iterator<int>(std::cout, "\n"));
    // ---

    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "Time with set_intersection: " << elapsed.count() << " ms\n\n";

    // 3. std::unordred_set
    start = std::chrono::system_clock::now();

    std::unordered_set<int> setArray1(std::begin(arr1),std::end(arr1));
    for (const int i : arr2) {
        if (setArray1.count(i)) {
            std::cout << i << '\n';
        }
    }

    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "Time with unordered set: " << elapsed.count() << " ms\n\n";
}