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;
}
分享到:
相关推荐
通过这样的位操作,我们可以在不使用额外的数据结构或排序的情况下,有效地找出数组中三个只出现一次的数字。这种方法充分利用了位操作的高效性,是解决这类问题的经典算法之一。在实际的面试或编程竞赛中,掌握这类...
在本问题中,我们面临的是一个经典的算法挑战:找出数组中三个数字的组合,使得它们的和为零。这个题目属于计算机科学中的“三数之和”问题,通常在算法设计和面试中出现,旨在考察候选人的逻辑思维和解决复杂问题的...
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请找出这两个只出现一次的数字。 # -*-coding:utf-8 -*- class Solution: def FindNumsAppearOnce(self, array): # 如果两个数相同,那么这两个数的...
给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数N(≤20),随后是N个整数,其间以空格分隔。 输出格式: 在一行中按照数字给出的...
在本题"剑指offer系利—–item38 找出数组中唯一的两个只出现一次的数字"中,我们需要解决的问题是,在一个整数数组里,有两个数字只出现一次,而其他所有数字都出现两次。我们的目标是找到这两个独特的数字。 解决...
总的来说,解决数组中出现一次的数字问题需要理解各种算法和数据结构的特性,并根据具体问题选择合适的方法。双循环简单但效率低,空间换时间方法在特定情况下有效,而异或操作则提供了高效的解决方案。在实际应用中...
已经两个已经排好序的数组,找出两个数组合起来的中间大的数字
给出一个递增数组array和由array中两个数的和n,求出这两个数? 求两个递增数组的最小距离,即在两个数组中各取一个数,使得这两个数的差最小? http://blog.csdn.net/ssuchange/article/details/17402991
题目要求在给定的整型数组 `nums` 中找出仅出现一次的两个数字,并返回这两个数字组成的数组。数组中所有其他元素都会出现两次。题目强调了时间复杂度必须为 O(n),空间复杂度应为 O(1)。这里的 n 表示数组 `nums` ...
- 使用两个嵌套循环遍历整个数组,外层循环迭代每一行,内层循环迭代每一行中的每个元素。 - 在每次循环中比较当前元素与已知的最大值,如果当前元素更大,则更新最大值及`index`数组。 - 循环结束后,`index`...
题目 "只出现一次的数字(分组+异或)1" 是 LeetCode 上的一个经典算法问题,要求在给定的整数数组 `nums` 中找出仅出现一次的两个元素。数组中其他元素均出现两次,返回这两个单次出现的元素,顺序不限。此题的关键...
在本问题中,我们关注的是如何找出一个正型数组中出现次数最多的前三个数。这涉及到数据统计、排序以及可能的哈希映射等技术。我们将探讨如何通过对象数组和自定义比较器来实现这一目标。 首先,创建一个对象数组,...
我们考虑如果每个数字都置出现一次,那么此时是最完美的,每一个下标i对应元素numbers[i],也就是说我们对于数组中的每个元素numbers[i]都把它放在自己应该在的位置上numbers[numbers[i]]上, 如果我们发现有两个元素...
关于如何用JavaScript实现找出数组中最长的连续数字序列,以下是一些重要的知识点。 首先,需要理解连续数字序列的定义:在一个整数序列中,连续数字是指按数值顺序排列,且数值相邻的数字序列。例如,序列[1, 2, 3...
1. **查找缺失的两个数字**:由于数组共有98个元素,而1到100一共有100个数,这意味着有两个数字不在数组中。我们可以使用哈希表或计数排序来快速找出缺失的数。 2. **验证数组是否包含所有数字**:可以通过遍历...
在这个例子中,`filter`方法配合`lastIndexOf`找出数组中每个元素首次出现的位置,如果当前位置等于最后一次出现的位置,说明这个元素是第一次出现,因此保留下来。 总的来说,`lastIndexOf`是JavaScript数组操作中...
我们通过比较 `indexOf()` 和 `lastIndexOf()` 的结果来确保元素只出现一次,这样就可以过滤出两个数组中的独特元素。 **2. 取出两个数组的相同元素:** ```javascript function getArrEqual(arr1, arr2) { let ...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 ...
在学习和使用这个方法时,还可以结合其他数组函数,如`array_unique`(去除重复元素)和`array_diff`(找出两个数组的差异),以实现更丰富的数组操作。同时,理解数据结构和算法对于优化这类问题的解决方案至关重要...
用户被要求输入一个数字,这个数字会存储在变量`key`中。 3. 折半查找循环: ```c while(left) { mid=(left+right)/2; if(key==s[mid]){printf("第%d 个元素的值\n",mid+1);break;} else if(key>s[mid])left...