問題描述

• 數(shù)組中只有一個數(shù)出現(xiàn)了奇數(shù)次，其它數(shù)都出現(xiàn)了偶數(shù)次，找到這個出現(xiàn)了奇數(shù)次的數(shù)

解決方法

• 方法1:循壞遍歷，統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)，直到找到出現(xiàn)奇數(shù)次的數(shù)
• 方法2:數(shù)組中所有數(shù)異或的結果就是出現(xiàn)奇數(shù)次的數(shù)

實現(xiàn)代碼

#include <stdio.h>

/* solution 1 */
int odd_times_num1(int *a, size_t len)
{
        int i, j, cnt;

        for(i=0; i<len; i++) {
                cnt = 1;
                for(j=0; j<len; j++) {
                        if(i == j) continue;
                        if(a[i] == a[j]){
                                cnt++;
                        }
                }
                if(cnt%2) break;
        }
        return a[i];
}

/* solution 2 */
int odd_times_num2(int *a, size_t len)
{
        int i, x = 0;

        for(i=0; i<len; i++) {
                x = x^a[i];
        }

        return x;
}

int main(int argc, char** argv)
{
        int i   = 0;
        int len = 0;
        int a[]={-1, 0, 1, -1, 0, 1, 3, 4, 3, 4, 1};

        len = sizeof(a)/sizeof(int);
        for(i=0; i<len; i++){
                printf("%2d ", a[i]);
        }
        printf("\n");

        printf("odd times num: %i\n", odd_times_num1(a, len));
        printf("odd times num: %i\n", odd_times_num2(a, len));
        return 0;
}

異或

• 還是異或大法好