【两日一练】学习记录

题目

1. （1）、有101个整数，其中有50个数出现了两次，一个数出现了一次，找出出现了一次的那一个数。
   （2）、有102个整数，其中有50个数出现了两次，两个数出现了一次，找出出现了一次的那两个数。

思路分析

1. （1）异或：相同数字得到0，任何数和零异或，最终得到自身，同时，异或满足【交换律】。通过这些特点，我们将101个数全部异或，就能找出出现一次的那个数。
   （2）采用分治法；
   首先将所有的数异或，因为有两个数出现一次，所以最终得到的异或结果，实际上是那两个出现一次的数的异或结果，由结果的最低位1可知，出现一次的那两个数这一位一定不同，因此拿这一位同所有的数按位与，为1的放到一堆，为0的放到另一堆，就能将这两个只出现一次的数分开，然后对两堆分别异或，就能找出只出现一次的那两个数。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define N 9
#define M 8


void the_one()
{
    int i,t=0,a[N];
    for(i=0;i<N;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<N;i++)
    {
        t=t^a[i];
    }
    printf("----------------\n");
    printf("%d\n",t);
}

void the_two()
{
    int i,a[M],t=0,pos;
    int b[2]={0};

    for(i=0;i<M;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<M;i++)
    {
        t=t^a[i];
    }
    pos=t&-t;//pos中存储了异或结果中的1的最低位
    for(i=0;i<M;i++)
    {
        if(pos&a[i])//如果1的最低位和数组的相对应的位置按位与为真（最终结果不为0）
        {
            b[0]=b[0]^a[i];
        }
        else{
            b[1]=b[1]^a[i];
        }
    }
    printf("----------------\n");
    for(i=0;i<2;i++)
    {
        printf("%3d",b[i]);
    }
    printf("\n");
}


int main()
{
    //第一小题
    the_one();
    //第二小题
    the_two();
    system("pause");
}

运行结果

• （PS：由于一组数的数量过多，这里分别以9、8个数分别验证代码可行性）
  （1）