一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个出现一次的数字

算法描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个出现一次的数字，要求时间复杂度为O(n),空间复杂度是O(1)

算法实现：

异或的性质：任何数字异或它自己都是0.

/*************************************************************************
> File Name: main.c
> Author: cyf
> Mail: 1097189275@qq.com
> Created Time: 2016年03月26日 星期六 13时34分26秒
************************************************************************/
#include <stdio.h>
/*
* 一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个出现一次的数字，要求时间复杂度为O(n),空间复杂度是O(1)
* 例如：[2, 4, 3, 6, 3, 2, 5, 5]->[4, 6]
* */
int main()
{
int data[8] = {
2, 4, 3, 6, 3, 2, 5, 5
};
int num1, num2;
FindNumsAppearOnce(data, 8, &num1, &num2);
printf("num1:%d,num2:%dn", num1, num2);
}

/*************************************************************************
> File Name: FindNumsAppearOnce.h
> Author: cyf
> Mail: 1097189275@qq.com
> Created Time: 2016年03月26日 星期六 13时40分16秒
************************************************************************/
#ifndef FINDNUMSAPPEARONCE_H
#define FINDNUMSAPPEARONCE_H
#include <stdio.h>
#include <stdlib.h>
void FindNumsAppearOnce(int *data, int length, int *num1, int *num2);
int FindFirstBitOf1(int num);
int IsBitOf1(int num, int indexOf1);
#endif

/*************************************************************************
> File Name: FindNumsAppearOnce.c
> Author: cyf
> Mail: 1097189275@qq.com
> Created Time: 2016年03月26日 星期六 13时40分08秒
************************************************************************/
#include "FindNumsAppearOnce.h"
void FindNumsAppearOnce(int *data, int length, int *num1, int *num2)
{
if(data==NULL ||length <0)
return ;
int resultOfxor = 0;
int i;
for(i=0; i<length; i++)
resultOfxor ^= data[i];
int locationOf1 = FindFirstBitOf1(resultOfxor);
*num1 = *num2 = 0;
for(i=0; i<length; i++)
{
if(IsBitOf1(data[i], locationOf1))
{
*num1 ^= data[i];
}
else
*num2 ^= data[i];
}
}
int FindFirstBitOf1(int num)
{
int indexOf1 = 0;
while(((num&1) == 0)&& indexOf1<8*sizeof(int))
{
num = num>>1;
++indexOf1;
}
return indexOf1;
}
int IsBitOf1(int num, int indexOf1)
{
int flag = 0;
if(((num>>indexOf1)&1) == 1)
flag = 1;
return flag;
}

CC = gcc
CFLAGS = -g
%.o:%.c
$(CC) -o $@ -c $(CFLAGS) $<
main:main.o FindNumsAppearOnce.o
$(CC) main.o FindNumsAppearOnce.o -o main $(CFLAGS)
clean:
rm -rf *.o main

最后

以上就是默默猫咪为你收集整理的一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个出现一次的数字的全部内容，希望文章能够帮你解决一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个出现一次的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。