/***********************************************************************
题目:一个整型数组除了两个数字之外,其他的数字都出现了两次。请写程序找出
这两个只出现一次的数字。要求时间复杂度是O(N),空间复杂度为O(1)。
***********************************************************************/
/*
解题思路:
由于其他数字都出现了两次,那么最终得到的结果就是两个只出现一次的数字的
异或结果。因为其他数字都出现了两次,在异或中全部抵消了。由于这两个数字
肯定不一样,那么异或的结果肯定不为0,也就是说在这个结果数字的二进制表示
中至少就有一位为1。我们在结果数字中找到第一个为1的位,记为第n位。现在我们
以第n位是不是1为标准把原数组中的数字分成两个子数组,第一个子数组中每个数
字的第n位都是1,而第二个子数组中每个数字的第n为都是0。由于我们分组的标准
是数字中的某一位是1还是0,那么出现了两次的数字肯定被分配到同一个数组。因
为两个相同的数字的任意一位都是相同的,我们不可能把两个相同的数字分配到两
个子数组中去,于是我们已经把原数组分成了两个子数组,每个字数组都包含一个
只出现一次的数字,而其他数字都出现了两次。我们已经知道如何在数组中找出
唯一一个只出现一次的数字,因此到此为止所有的问题都已经解决了。
举个例子:
假设输入数组{2,4,,6,3,2,5,5}。当我们依次对数组中的每一个数字做异或运算之后,
得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1,于是我们根据数
字的倒数第二位是不是1分成两个数组。第一个子数组{2,3,6,3,2}中所有数字的倒数
第二位都是0。接下来只要分别对这两个子数组求异或,就能找出第一个子数组中只
出现一次的数字是6,而第二个子数组中只出现一次的数字是4。
*/
#include<stdio.h>
unsigned int findFirstBitIs1(int num);
bool IsBit1(int num, unsigned int indexBit);
void findNumAppearOnce(int* data,int length,int* num1,int* num2)
{
if(data == NULL || length<2)
return;
int resultExclusiveOR = 0;
for(int i=0; i<length; ++i)
resultExclusiveOR ^= data[i];
unsigned int indexOf1 = findFirstBitIs1(resultExclusiveOR);
*num1 = *num2 = 0;
for(int j=0; j<length; ++j)
{
if(IsBit1(data[j],indexOf1))
*num1 ^= data[j];
else
*num2 ^= data[j];
}
}
//找到所有数字异或后的结果,最先出现1的位置
unsigned int findFirstBitIs1(int num)
{
int indexBit = 0;
while(((num & 1) == 0) && (indexBit < 8 * sizeof(int)))
{
num = num>>1;
++indexBit;
}
return indexBit;
}
//判断数字num上第indexBit位是不是为1。
bool IsBit1(int num, unsigned int indexBit)
{
num = num >> indexBit;
return (num & 1);
}
void test()
{
const int length = 8;
int arr[length] = {2,4,3,6,3,2,5,5};
int num1 = 0;
int num2 = 0;
findNumAppearOnce(arr,length,&num1,&num2);
printf("%d\t%d\n",num1,num2);
}
int main()
{
test();
return 0;
}
==参考剑指offer
分享到:
相关推荐
java基础面试题数组中只出现一次的数字本资源系百度网盘分享地址
数组中只出现一次的两个数字.md
请找出这两个只出现一次的数字。 # -*-coding:utf-8 -*- class Solution: def FindNumsAppearOnce(self, array): # 如果两个数相同,那么这两个数的异或操作就等于0 if len(array) > 1 count += 1 mask = 1 <...
数组中唯一只出现一次的数字.md
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
本文实例讲述了PHP查找数组中只出现一次的数字实现方法。分享给大家供大家参考,具体如下: 问题: 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 实现代码如下:...
定义一个方法传入一个 int 类型数组,输出这个数组中每一个数字及其出现的个数 例如 传入数组[1,2,2,2,3,3,4,4,4,4] 打印结果: 数字 1 出现了 1 次 数字 2 出现了 3 次…
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
数组中数字出现的次数 II在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。示例 1:输出:4示例 2:输出:1int singleNum
# 在一个数组中除了一个数字只出现1次外,其他均出现2次,求这个数字
请写程序找出这两个只出现一次的数字。 分析 要解这题需要对异或操作有比较深的理解。 依次将数组中所有元素进行异或得到a,即num1和num2的异或。然后取a中二进制为1的一个位置,找到原数组中所有该位为1的数字进行...
剑指offer面试题库中第三题的C语言代码。在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
一个给定的正整数数组,数组中有的数字有重复,找出数组中没有重复的数
HashMap用桶的话会有一个问题,加入这个数组的取值范围是0~9999,数组的组成是{1,2,9998,2,1},我们为了把5个数中间单独出现的那一个数取出来
/*找出一个数组中的两个唯一出现过一次的数字,其他数组都出现了两次。 思路:还是和当时的那道题目一样,用HashMap记录每个数字出现的次数,返回唯一两个get为0的数,加个flag分开即可*/ public class item38 { ...
程序员面试题100题(63)-数组中三个只出现一次的数字[算法].pdf,这是一份不错的文件
面试题56 - I. 数组中数字出现的次数题目链接面试题56 - I. 数组中数字出现的次数题目描述一个整型数组里除了两个数字之外,其他的数字都出现了两次。传出
题目描述剑指 Offer 56 - I. 数组中数字出现的次数一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。示例 1:输出:[1,6] 或
文章目录在其他数都出现偶数次的数组中找到出现奇数次的数整型数组中其他数都出现偶数次找到唯一出现奇数次的数题目算法思路相应代码整型数组中其他数都出现偶数次找到两个出现奇数次的数题目算法思路相应代码 ...