408-数据结构-三个相同的元素

王道书习题2.2.3 应用题09

给定三个序列A，B，C，长度均为n，且为均匀无重复递增序列，请设计一个时间上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如数组A为{1,2,3}，B={2,3,4}，C={-1,0,2}，则输出2。

解法一：暴力枚举

void sameKey(vector<int> a,vector<int> b,vector<int> c,int n){
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (a[i] == b[j] && b[j] == c[k]){
                    printf("%d \n",a[i]);
                }
            }
        }
    }
}

时间复杂度：O(N^3)；

空间复杂度：O(1);

解法二：指针

使用三个下标变量从小到大遍历数组。当三个元素相等时，输出并向前推进指针，否则仅移动小于最大元素的下标数量，知道某个下标超出数组范围，即可停止。

void sameKey2(vector<int> a,vector<int> b,vector<int> c,int n){
    int i=0,j=0,k=0;
    while (i<n&&j<n&&k<n){
        if (a[i] == b[j] && b[j]==c[k]){
            printf("%d\n",a[i]);
            i++,j++,k++;
        }else{
            int maxNum = max(a[i], max(b[j],c[k]));
            if (a[i] < maxNum) i++;
            if (b[j] < maxNum) j++;
            if (c[k] < maxNum) k++;
        };
    }
}

时间复杂度：O(N)

空间复杂度：O(1)