从103个数中找到出现一次的那三个数

1、从101个数中找到出现一次的那1个数？

eg：[5,7,6,7,5] 找到6

//101
void demo01() {
    
    int arr[5] = {
     5,7,6,7,5 };
	
    int result;
    result = 0;
    for (int i = 0; i < 5; i++) {
    
        result ^= arr[i];
    }
    
    printf("出现一次的那个数=%d\n", result);
}

通过异或操作，就可以找到唯一出现的那个数；

2、从102个数中找到出现一次的那2个数？

eg：[5,7,6,7,5,8] 找到 6，8

//101
int demo01(int arr[]) {
    
    //int arr[5] = { 5,7,6,7,5 };

    int result;
    result = 0;
    for (int i = 0; i < 6; i++) {
    
        result ^= arr[i];
    }
    
    //printf("出现一次的那个数=%d\n", result);
    return result;
}

//102
void demo02() {
    
    
    int arr[6] = {
     5,7,6,7,5,8 };
    int flag = demo01(arr);
    int split_val = flag & (-flag);
    printf("%d\n", split_val);
    int res1, res2;
    res1 = 0; res2 = 0;    
    for (int i = 0; i < 6; i++) {
    
        if (arr[i]&split_val) {
    
            res1 ^= arr[i];
        }else {
    
            res2 ^= arr[i];
        }
    }
    printf("第一个数=%d,第二个数=%d\n", res1,res2);
}

1、通过所有值得异或就可以找到在两个不同数之间的不同；
2、通过flag & (-flag)操作可以找到所有值得异或结果的最低位的1；
3、通过和最低位的1与操作，可以把两个不同的数分开；一个为真，一个为假；

3、从103个数中找到出现一次的那3个数？

eg: [5,7,6,7,5,8,9]找到6，8，9

//102
void demo02(int arr[],int even,int odd) {
    
    
    int split_val = even & (-even);
    //printf("%d\n", split_val);
    int res1, res2;
    res1 = 0; res2 = 0;    
    for (int i = 0; i < 7; i++) {
    
        if (arr[i]&split_val) {
    
            res1 ^= arr[i];
        }else {
    
            res2 ^= arr[i];
        }
    }
    if (split_val& odd) {
    
        res1 ^= odd;
    }else {
    
        res2 ^= odd;
    }
    printf("第二个数=%d,第三个数=%d\n", res1,res2);
}

//103
void demo03() {
    
    int arr[7] = {
     5,7,6,7,5,8,9 };
    int res1, res2,count1,count2;
    int flag;
    flag = 1;
    for (int i = 0; i < 32;i++) {
    
        res1=res2=count1=count2 = 0;
        for (int j = 0; j < 7; j++) {
    
            if (flag&arr[j]) {
    
                res1 ^= arr[j];
                count1++;
            }else {
    
                res2 ^= arr[j];
                count2++;
            }    
        }
        //判断偶数是否大于0
        if (count1 % 2 == 0 && res1!=0) {
    
            printf("第一个数=%d", res2);
            demo02(arr, res1, res2);
            break;
        }
        else if (count2 % 2 == 0 && res2 != 0) {
    
            printf("第一个数=%d", res1);
            demo02(arr, res2, res1);
            break;
        }
        //如果没找到 0 3 
        flag << 1;
    }
}

1、首先，使用暴力法，从1开始，每次向左移动1位二进制位，到32位也就是移动31位；
2、就把把那三个单独的数分成2堆，只有两种情况；奇数堆：偶数堆 = 3 ：0 或 1：2；
3、只需要判断偶数堆的异或操作不为0，也就是说是1：2这种情况；就找到了在奇数堆中的一个单数；
4、通过demo02函数；思想和第2题一样，但是因为有103个数，所以第三个单数会被分配到其中一边；
5、我们需要判断这个数，是在奇数堆还是在偶数堆，通过split_val & odd判断是在那一边，就可以在异或一次，就可以消除这个数；