找出只出现一次的数字

题目

给定一个非空整型数组，除了某个元素只出现一次以外，其余每个元素均出现两次，找出那个只出现了一次的元素

int a[]={1，2，3，4，5，1，2，3，4}；该数组只有5出现一次，其他数组都是成对的出现，要求找到5

思路一

#include<stdio.h>
int main()
{
  int arr[]={1,2,3,4,5,1,2,3,4};
  int i=0;//下标
  int sz=sizeof(arr)/sizeof(arr[0]);
  for(i=0;i<sz;i++)
  {
    int count=0;
    int j;
    for(j=0;j<sz;j++)
    {
      if(arr[i]==arr[j])
      {
        count++;
      }
    }
    if(count==1)
    {
      printf("找到了：%d\n",arr[i]);
      break;
    }
  }
  return 0;
}

关键部分：

for(i=0;i<sz;i++)
  {
    int count=0;
    int j;
    for(j=0;j<sz;j++)
    {
      if(arr[i]==arr[j])
      {
        count++;
      }
    }
    if(count==1)
    {
      printf("找到了：%d\n",arr[i]);
      break;
    }
  }

其中两个for的目的是使在每一个大循环前提下找到是否有与这个大循环的数相等的值 这个值在小循环里依次进行了循环

count用来记录每个数出现的次数，如果是1那就是所需要的数

算法缺陷：运行效率太低

思路二

#include<stdio.h>
int main()
{
  int arr[]={1,2,3,4,5,1,2,3,4};
  int i;
  int sz=sizeof(arr)/sizeof(arr[0]);
  int ret=0;
  for(i=0;i<sz;i++)
  {
    ret=ret^arr[i];
  }
  printf("%d\n",ret);
  return 0;
}

主要部分：

  for(i=0;i<sz;i++)
  {
    ret=ret^arr[i];
  }

异或：按二进制位进行 相同为0 相异为1；满足交换律

a^a=0; a^0=a  

所以：1^1^2^2^3^3^4^4^5=5

缺陷：这是针对题目的算法 只能在其中找到一个只出现一次的数