1,题意:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
2,分析:
(1)各个元素依次异或,得到两个数字异或的结果 val.
(2)找到val的一个bit为1的位.
(3)根据上述比特位1或0将原来的数组分成两组.
(4)每组异或,即可得到要求的数.
3,实例代码:
#include <iostream>
#include <cstring>
using namespace std;
void findOnce(int data[], int n, int &num1, int &num2)
{
if (n < 5)
return;
int r1 = 0;
for (int i = 0; i < n; i++)
r1 ^= data[i];
int bitNum = 0;
while ( !(r1 & 0x1))
{
r1 >>= 1;
++bitNum;
}
int flag = (1 << bitNum);
num1 = 0;
num2 = 0;
for (int i = 0; i < n; i++)
{
if ( data[i] & flag)
num1 ^= data[i];
else
num2 ^= data[i];
}
}
int main()
{
int data[] = {1,1,2,3,3,4,5,5};
int num1, num2;
findOnce(data, sizeof(data)/sizeof(data[0]), num1, num2);
cout << num1 <<" " << num2 << endl;
return 0;
}
分享到:
相关推荐
一个数组,仅有两个数字出现一次,其他都是两次,找出这两个数字 思路: 思路:还是和当时的那道题目一样,用HashMap记录每个数字出现的次数,返回唯一两个get为0的数,加个flag分开即可 整合以上思路后,源码如下:...
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请找出这两个只出现一次的数字。 # -*-coding:utf-8 -*- class Solution: def FindNumsAppearOnce(self, array): # 如果两个数相同,那么这两个数的...
给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数N(≤20),随后是N个整数,其间以空格分隔。 输出格式: 在一行中按照数字给出的...
已经两个已经排好序的数组,找出两个数组合起来的中间大的数字
给出一个递增数组array和由array中两个数的和n,求出这两个数? 求两个递增数组的最小距离,即在两个数组中各取一个数,使得这两个数的差最小? http://blog.csdn.net/ssuchange/article/details/17402991
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 实现代码如下: <?php function FindNumsAppearOnce($array) { // write code here // return list, 比如[a,...
主要介绍了C语言中找出数组中特定元素的算法解析,包括找出数组中两个只出现一次的数字的方法,需要的朋友可以参考下
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 分析 要解这题需要对异或操作有比较深的理解。 依次将数组中所有元素进行异或得到a,即num1和num2的异或。然后取a...
我们考虑如果每个数字都置出现一次,那么此时是最完美的,每一个下标i对应元素numbers[i],也就是说我们对于数组中的每个元素numbers[i]都把它放在自己应该在的位置上numbers[numbers[i]]上, 如果我们发现有两个元素...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 ...
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 解题思路:要求时间复杂度为o(n),空间复杂度O(1),如果没有这些要求,...
主要介绍了JS取出两个数组中的不同或相同元素,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
5.19 已知数组A包含15个互不相等的整数,试编写一程序,把既在A中又在B中出现的整数存在于数组中C中。 5.20 设在A,B和C单元中存放着三个数,若三个数都不是0,则求出三树之和并存放于D单元中;其中有一个数为0,则把...
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 两种方式: 1...
1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
# 有序数组的平方 ...# 方法比较多, 比如先找出最中心的数字后转换成两个数组进行归并运算, 但是双指针方法是最简单的 # 截止条件定在为正负分界线上, 一旦达到表示其中一个数字遍历完毕, 剩下的直接进行追加即可
首先看到这题,我们需要找到那个唯一的只出现一次的数字,而其他的数字都是只出现了两次,那么我们如果一个一个的去数组里找是否有重复的,这样时间复杂度会很大,所以我们要想如何更加简单的找出唯一的只出现一次的...
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 示例 1: 输入:nums = [4,1,4,6] 输出:[1,6] 或 [6,1] 示例 2: ...
下面小编就为大家分享一篇java 判断一个数组中的数值是否连续相邻的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路...