有没有办法忽略数组中的元素而不更改递归函数中的数组？

Question

我正在尝试编写一个递归函数,检查两个数组是否具有相同的元素,即使它们没有排序,但是我不能更改数组,我无法复制它们或使用第三个/第四个数组而且它必须是递归的,最后,我无法更改函数的签名.

所以现在我必须摆脱overwrite(A2, len, i);因为那是在破坏A2,但是我没有看到任何方法去做它仍然有一个有效的功能......我可以提示如何做到这一点吗？也许有一种方法可以A2通过交换它们来保存元素,然后在递归结束时恢复它们？

简而言之,下面的算法对A2中A1的最后一个元素进行线性搜索,如果找到它,覆盖它并继续,这样就完成了,因此算法不会选择相同的元素两次,达到停止条件意味着所有元素因此它会返回true,否则将返回false.

bool foo(int A1[], int A2[], int len){//both arrays are size len

    int i;
    bool found = false;

    if (len == 0)return true;//stopping condition for recursion
    else{
        for (i = 0; i < len && !found; i++)//linear search
            if (A1[len - 1] == A2[i]){
                overwrite(A2, len, i);//this function shifts back the whole array
                found = true;
            }

        if (found == false) return false;
        else foo(A1, A2, len - 1);

    }
}

样本i/o:

A1:    3   2   1
A2:    1   2   3
True

A1:    3   2   3
A2:    1   2   3
False

Answer 1

解决方案可能是:

1. 发现什么是最大值M,在A1它出现了多少次
2. 检查它是否相同A2,包括计数
3. 找到M1小于MA1的所有值中的最大值以及A1中存在的次数
4. 检查它是否相同A2,包括计数
5. 找到M2小于M1A1的所有值中的最大值以及A1中存在的次数
6. 检查它是否相同A2,包括计数
7. 重复这种方式,直到计数器为A1和A2为零或不同

在代码中:

bool checkSame(int *A1, int *A2, int len) {
    struct Same {
        static bool check(int *A1, int *A2, int len, int limit) {
            int index1=-1, count1=0;
            for (int i=0; i<len; i++) {
                if (A1[i] <= limit) {
                    if (index1==-1 || A1[i] > A1[index1]) {
                        index1 = i;
                        count1 = 1;
                    } else if (A1[i] == A1[index1]) {
                        count1++;
                    }
                }
            }
            int index2=-1, count2=0;
            for (int i=0; i<len; i++) {
                if (A2[i] <= limit) {
                    if (index2==-1 || A2[i] > A2[index2]) {
                        index2 = i;
                        count2 = 1;
                    } else if (A2[i] == A2[index2]) {
                        count2++;
                    }
                }
            }
            if (index1 == -1 && index2 == -1) return true;
            if (count1 != count2 || count1 == 0 ||
                A1[index1] != A2[index2]) return false;
            return check(A1, A2, len, A1[index1]-1);
        }
    };
    return Same::check(A1, A2, len, INT_MAX);
}

该算法及时为O(n ^ 2)(最坏情况:数组相同且所有值都是唯一的)并且如果编译器支持尾调用优化则需要恒定空间.

以下是我的PC上0到3000个元素所需时间的图表.

请注意,然而这一切并不是解决问题的理想方案,而只是徒劳无功.一个真正的解决方案当然需要更多的上下文,因为有不同的最优性标准,但我可能会选择一个封闭的哈希表...在处理A1时添加元素并删除处理A2的元素(如果删除元素会在某些时候失败并且只有当数组不同时):

bool checkSame2(int *A1, int *A2, int len) {
    std::vector<int> ht(len, -1), next(len, -1);
    for (int i=0; i<len; i++) {
        int k = (unsigned)A1[i]*69069 % len;
        next[i] = ht[k]; ht[k] = i;
    }
    for (int i=0; i<len; i++) {
        int k = (unsigned)A2[i]*69069 % len;
        int prev=-1,p=ht[k];
        while (p!=-1 && A1[p] != A2[i]) {
            prev = p; p = next[p];
        }
        if (p == -1) return false;
        if (prev == -1) ht[k] = next[p]; else next[prev] = next[p];
    }
    return true;
}

此解决方案的执行时间是紫色线在前一个图表中触及N轴(很难用这个比例来判断,但它是线性+噪声,如预期的那样).

出于好奇,我还尝试了什么是解决方案,如果"最佳"意味着只是让一些工作不那么可怕:

bool checkSame3(int *A1, int *A2, int len) {
    std::map<int, int> counts;
    for (int i=0; i<len; i++) counts[A1[i]]++;
    for (int i=0; i<len; i++) {
        if (--counts[A2[i]] < 0) return false;
    }
    return true;
}

毫无疑问,这比我手机上编写的手写代码哈希表版本快30-40倍(但当然仍然比递归版本快得多).