比较数组并找到相同的数据计数

Question

#include <stdio.h>

int main()
{
    int a, b, arr1[100000], arr2[100000], cnt=0;
    scanf("%d %d", &a, &b);
    for(int i = 0; i < a; i++)
    {
        scanf("%d", &arr1[i]);
    }
    for(int i = 0; i < b; i++)
    {
        scanf("%d", &arr2[i]);
    }

    for(int i = 0; i < a; i++)
    {
        for(int j = 0; j < b; j++)
        {
            if(arr1[i] == arr2[j]) cnt++;
        }
    }
    printf("%d", cnt);
}

这是在arr1和arr2中查找相同数据数量的代码，a和b是arr1和arr2中数据的数量。

例如，第一行输入 3 3 并102030112030

输入，

arr1是[10, 20, 30]，arr2是[11, 20, 30]，相同的数据数是2。有没有办法让算法更快？

任何帮助都会很棒!谢谢!

[已解决]使用二分搜索

#include <stdio.h>
#include <algorithm>

using namespace std;

int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l)
    {
        int mid = l + (r - l)/2;
        if (arr[mid] == x)  return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, r, x);
    }
    return -1;
}

int main(void)
{
    int arr1[100001], arr2[100001], cnt=0, a, b;
    scanf("%d %d", &a, &b);

    for(int i = 0; i < a; i++) scanf("%d", &arr1[i]);
    for(int i = 0; i < b; i++) scanf("%d", &arr2[i]);

    sort(arr1, arr1+a);
    sort(arr2, arr2+b);

    for(int i = 0; i < a; i++)
    {
        int result = binarySearch(arr1, 0, a, arr2[i]);
        if(result != -1) cnt++;
    }
    printf("%d", cnt);
    return 0;
}

Answer 1

现在这个问题的答案完全取决于您的输入限制是什么。在您的情况下，数组 a 和 b 的大小起着最关键的作用。

现在，如果要对两个数组进行排序，复杂度将是 O(alog(a)) 或 O(blog(b))，以较大者为准。但在你的情况下，复杂度是 O(a*b)。

现在的问题是，排序的复杂度是 a*b > 吗？如果一般情况下不是这样，最好坚持以前的方法，因为不会增加开销，否则您可以使用排序和二分搜索。

注意:算法无法做得很快，您可以使用另一种时间复杂度较低的算法。

我通常使用 O() 表示法只是为了避免任何进一步的混淆，所以如果我错了，请耐心等待。