查找出现一次的元素
给定一个数组，其中每个元素都出现 3 次，除了一个元素只出现一次。找到出现一次的元素。
预期时间复杂度为 O(n) 和 O(1) 额外空间。
例子：
输入：arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
输出：2
问问题
16963 次
10 回答
12
如果不存在 O(1) 空间约束，那么您可能已经使用了值作为出现次数的哈希图。
int getUniqueElement(int[] arr)
{
int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once.
int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice.
int not_threes ;
for( int x : arr )
{
twos |= ones & x ; //add it to twos if it exists in ones
ones ^= x ; //if it exists in ones, remove it, otherwise, add it
// Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero.
not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes.
ones &= not_threes ;//remove x from ones
twos &= not_threes ;//remove x from twos
}
return ones;
}
基本上，它利用了x^x = 0和0^x=x. 所以所有成对的元素都会被异或并消失，留下孤独的元素。
简而言之 ：
如果一个位已经在一个中，则将其添加到两个中。
如果它不存在，XOR 会将这个位添加到那些，或者如果它已经存在，则从这些位中删除这个位。
如果一个位在一个和两个中，从一个和两个中删除它。
完成后，ones 包含仅出现 3*n+1 次的位，即仅出现一次的元素的位。
于 2012-12-31T10:39:36.873 回答
5
JavaScript 解决方案：
function findElement(arr) {
var ones = 0;
var twos = 0;
for (var i = 0; i < arr.length; i++) {
ones = (ones ^ arr[i]) & ~twos;
twos = (twos ^ arr[i]) & ~ones;
}
return ones;
}
于 2014-11-29T03:48:10.243 回答
2
如此处所述，可以在最坏情况 O(n) 时间和 O(1) 额外空间中找到数组元素的中值。所以我们可以用分治法来解决这个问题：
在 O(n) 时间内找到中位数并计算 O(n) 中小于或等于中位数的元素数。如果这个数字是 3k+1，则表示答案小于或等于中位数，所以在 O(n) 中省略大于中位数的元素。否则，省略那些小于或等于中位数的。然后递归地在 T(n/2) 的剩余元素中找到答案。注意：剩余元素的数量是 n/2，因为我们省略了一半的元素。
所以 T(n) = T(n/2)+O(n) = O(n) 我们需要 O(1) 额外的空间。
于 2012-12-31T12:47:13.777 回答
2
// as we know every number is present thrice except one number means that if we observe the bits at each place we will find that the set bits at each place are either multiple of 3n or 3n+1 ( when unique num has set bit at that place )
前 - 12、1、12、3、12、1、1、2、3、3
12- 1 1 0 0
1 - 0 0 0 1
12- 1 1 0 0
3 - 0 0 1 1
12- 1 1 0 0
1 - 0 0 0 1
1 - 0 0 0 1
2 - 0 0 1 0
3 - 0 0 1 1
3 - 0 0 1 1
3 3 4 6 ( 3n or 3n+1 ) form
它是 3n+1 形式的地方意味着唯一编号在这里设置了位，所以现在我们很容易提取唯一编号，因为我们知道它的设置位位置。
#include<iostream>
using namespace std;
int main() {
int n,num,j;
int set[64]={0}; // maximum bits
cin>>n;
for(int i=0;i<n;i++){
cin>>num;
j=0;
while(num){
set[j]+=(num&1);
num=num>>1;
j++;
}
}
int ans=0,p=1;
for(int i=0;i<n;i++){
ans+=(set[i]%3)*p;
p=p*2;
}
cout<<ans<<endl;
}
于 2021-03-12T03:25:13.560 回答
1
我提出了一个类似于 mhsekhavat 提出的解决方案。我建议使用荷兰国旗问题的划分算法而不是确定中位数http://en.wikipedia.org/wiki/Dutch_national_flag_problem（是的，我是荷兰人并且接受了 Dijkstra 风格的教育）。
应用该算法的结果是一个分成红色、白色和蓝色部分的数组。白色部分可以被认为是枢轴。请注意，白色部分由等于枢轴的所有元素组成，因此白色部分将包含 1 或 3 个元素。红色部分由小于枢轴的元素组成，蓝色部分由大于枢轴的元素组成。（注意红蓝部分没有排序！）
接下来，计算红色、白色和蓝色部分的元素数量。如果任何部分由 1 个元素组成，那么这就是您要查找的数字。否则，对于给定数量的 k，红色或蓝色部分由 3k+1 个元素组成。对包含 3k+1 个元素的部分重复该算法。最终其中一个零件的尺寸为 1。
该算法在 O(n) 中运行并且需要 O(1) 个变量。
于 2012-12-31T14:53:51.287 回答
1
尽管问题已经得到解答，但我发现以下内容更直观，因此将其添加为答案。最初从这里
int singleNumber(vector<int>& nums) {
/*Bits in 'ones' are set to 1, when that particular bit
occurs for the first time. Bits in 'twos' are set to 1,
when that particular bit occurs for the second time. If a
bit is occurring for more than 2 times, we throw it away
and start counting again.*/
int ones = 0;
int twos = 0;
for (auto elem : nums) {
int onesOld = ones;
/* (ones ^ elem): consider the ith bit in 'ones' be 0 (i.e. ith
bit has not occurred till now or has occurred 2 times) and in
'elem' be 1. So, for the ith bit (ones ^ elem) gives 1. Now,
ith bit could have occurred even number of times as well (i.e.
ith bit in twos is set to 1). If that was the case, we
would like to ignore such bit. This last part is taken care
of by '&' with '~twos'
*/
ones = (ones ^ elem) & ~twos;
/* (onesOld & elem) gives the bits which have occurred ones
and also occur in this particular element. (twos & ~elem)
gives the bits that have occurred twice and do not occur
in this element. Both these cases take care of the bits
that have occurred 2 times (although a bit might be set
more than 2 times, like 5,7... but we take only modulo 3
count).
*/
twos = (onesOld & elem) | (twos & ~elem);
}
return ones;
}
于 2016-10-02T06:23:43.807 回答
0
考虑它们的二进制表示并将每个位置的位数相加。例如 [ 1, 1, 1, 2, 2, 2, 3] 给出 [4, 4]，只考虑表示这些数字所需的两位。取其中的 mod 3 给出 [1,1] ，它是二进制的 11 = 3，这是正确的答案。这仍然是 O(1) 空间，因为它不随元素数量而缩放，但仍然可能有一个巨大的前置因子。
一些草率的cpp代码：
int l = arr.size();
int nbits = 32;
vector<int> bits(nbits,0);
for( int i = 0; i < l; i++ ){
for( int j = 0; j < nbits; j++ ){
bits[j] += ( A[i] >>j ) & 1;
}
}
int missing = 0;
for( int j = 0 ; j < nbits; j++ ){
if( bits[j]%3 == 1 ){
set_bit( missing, j );
}
}
几乎可以肯定，这可以由比我更了解按位运算的人来优化（没有人喜欢循环中的循环......）。无论如何，我认为这应该适用于任何“k-duplicates 除了其中一个”类型的问题，假设丢失的只出现一次。
编辑：Leo Polovets 在这里也详细说明了这个答案 https://www.quora.com/Given-an-integer-array-such-that-every-element-occurs-3-times-except-one-element-仅发生一次，我如何在 O-1 空间和时间复杂度中找到单个元素
于 2018-11-16T07:06:18.800 回答
0
最好的解决方案是使用 XOR。所有数组元素的 XOR 为我们提供了一次出现的数字。这个想法是基于以下两个事实。a) 一个数与自身的 XOR 是 0。 b) 一个数与 0 的 XOR 是数字本身。
int findSingle(int ar[], int ar_size)
{
// Do XOR of all elements and return
int res = ar[0];
for (int i = 1; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
于 2020-05-13T11:13:01.410 回答
-2
将每个数字相加一次并将总和乘以 3，我们将得到数组中每个元素的总和的三次。将其存储为 thrice_sum。从 thrice_sum 中减去整个数组的总和，然后将结果除以 2。我们得到的数字就是所需的数字（在数组中出现一次）。
def singlenumbers(arr):
return (3* sum(set(arr)) - sum(arr))//2
arr = [6, 1, 3, 3, 3, 6, 6]
print(singlenumbers(arr))
于 2019-01-08T20:47:30.960 回答
-3
def apperasonce(arr1):
n=len(arr1)
for i in range(0,n):
if arr1.count(arr1[i]) == 1:
return arr1[i]
arr1=[12,1,12,3,12,1,1,2,3,3]
a=apperasonce(arr1)
print(a)
于 2018-07-06T19:04:40.203 回答