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。