首页 > 代码库 > 编程算法 - 数组中只出现一次的数字 代码(C)
编程算法 - 数组中只出现一次的数字 代码(C)
数组中只出现一次的数字 代码(C)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 一个整型数组里除了两个数字以外, 其他的数字都出现了两次. 请写程序找出这两个只出现一次的数字.
如果从头到尾依次异或数组中的每一个数字, 那么最终的结果刚好是那个只出现一次的数字.
根据结果数组二进制某一位为1, 以此分组, 为1的一组, 为0的一组, 再重新进行异或. 最后得出两个结果.
时间复杂度O(n).
代码:
/* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <stdlib.h> #include <string.h> size_t FindFirstBitIs1(int num) { size_t indexBit = 0; while ((num&1)==0 && indexBit<(8*sizeof(int))) { num >>= 1; ++indexBit; } return indexBit; } bool IsBit1(int num, size_t indexBit) { num >>= indexBit; return (num&1); } void FindNumsApprearOnce(int data[], int length, int* num1, int* num2) { if (data =http://www.mamicode.com/= NULL || length <= 0)>
输出:num1 = 6 num2 = 4
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。