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;

I didn’t read your program, but at least, you are wrong in the above code
if (k==10)

Answer 2

The fastest way is to sort and compare one by one, the time complexity is 2NlogN + N

Answer 3

Fastest method:

Use a hash table ht, the key is the array element type, and the value is int.

Traverse array a, for element i, ht[i]++; traverse array b, for element i in b, ht[i]--.

Just determine whether there is an item with a value other than 0 in ht. Complexity O(N)

Answer 4

I do not provide other algorithms.
As far as your thoughts on the topic are concerned, of course, this is a legendary violent method with little content.
But, the questioner, if you compare one by one like this, can you end the comparison as long as you find that there are unequal ones? Just return 0 directly.

Answer 5

First calculate the sum of the array and record the number of 0s.
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;
Then each comparison, equal Just set 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;
}
}
Then see if s2 has a non-0 value.
for(int j=0;j<10;j++)if(s2[j])return false;
This changes the s2 array. If the change is not allowed, a temporary s3 is generated.

Answer 6

If you don’t want to sort or use a hash table, you can try this method:

1. Suppose i = -1, n is the length of s1 and s2;

2. Sum the elements in arrays s1 and s2 respectively;

3. Compare whether their sums are the same. If the sums are not the same, then s1 and s2 are not the same, and the program terminates, otherwise i++;

4. If i == n - 1, then s1 is the same as s2 and the program terminates;

5. Subtract s1[i] from the elements in s1 and s2 respectively, and then return to step 2.