c++ - 用C语言确定两个数组内的元素排列顺序不同，但是元素相同，代码有bug找不出？

Question

我觉得稍微麻烦一点的就是允许数组内有重复，我想了两个办法，一种是排序好再挨个比较。另外一个我写了出了，但是跑不正确，怎么弄k都等于10，代码如下，请看出bug的大神指点：

int thr_bg(int s1[],int s2[]){
    int q,w,k=0;
    for (q=0; q<10; q++) {
        for (w=0; w<10 && s1[q]!=s2[w]; w++);
        // 找出与数组1第一个相同元素的位置
            if (w<10) {
                for (; w<10; w++) {
                    s2[w]=s2[w+1];
                }
                //把数组1第一个相同元素剔除，后面的元素依次向前
                k++;
                //记录与数组1第一个相同元素的个数
            }
    }
    printf("%d\n",k);
    if (k=10) {   //如果有十个相同元素，就代表完全相同
        return 1;
    }
    else return 0;
}

int main(){
    int s1[10],s2[10],i,j;
    printf("s1:");
    for (i=0; i<10; i++) {
        scanf("%d",&s1[i]);
    }
    printf("s2:");
    for (j=0; j<10; j++) {
        scanf("%d",&s2[j]);
    }
    if (thr_bg(s1,s2))
        printf("yiyang");
    else printf("buyiyanga");
}

另外，还有什么其他的实现方法推荐吗？

Answer 1

if (k=10) {   //如果有十个相同元素，就代表完全相同
        return 1;

我没看你的程序，但至少，上面代码你错了
if (k==10)

Answer 2

最快的办法就是排序,挨个对比, 时间复杂度 2NlogN + N

Answer 3

最快的方法:

用一个哈希表ht，键为数组元素类型，值为 int。

遍历数组 a，对于元素i，ht[i]++;遍历数组b，对于b中元素i，ht[i]--。

判断ht中是否有值不为0的项即可。复杂度O(N)

Answer 4

我不提供别的算法。
单单就题主你的想法而言，当然，这是传说中的暴力法，没什么含量。
但是，题主啊，你这样一个一个的比较，是不是只要发现有不相等的就可以结束比较了啊，直接返回0就可以了。

Answer 5

先计算数组的和并且记录为0的个数。
unsigned long sum1=0;
int zero1=0;
for(int i=0;i<10;i++){
if(s1[i])sum1+=s1[i];
else zero1++;
}
unsigned long sum2=0;
int zero2=0;
for(int i=0;i<10;i++){
if(s2[i])sum2+=s2[i];
else zero2++;
}
if(zero1!=zero2 || sum1!=sum2)return false;
然后每个比较，相等就设置0；
for(int i=0;i<10;i++){
int v=s1[i];
if(!v)continue;
for(int j=0;j<10;j++){
if(v==s2[j])s2[j]=0;
}
}
然后看看s2是否有非0值。
for(int j=0;j<10;j++)if(s2[j])return false;
这个改变了s2数组，如果不允许改变，临时生成一个s3.

Answer 6

不想排序也不想用 hash 表，可以试试这个方法：

1. 设 i = -1，n 为 s1 与 s2 的长度;

2. 对数组 s1 与 s2 中的元素分别求和；

3. 比较它们的和是否相同，若和不相同，则 s1 与 s2 不相同，程序终止，否则 i++；

4. 若 i == n - 1，则 s1 与 s2 相同，程序终止；

5. s1 与 s2 中的元素分别减去 s1[i]，然后再回到步骤 2。