Единственное вхождение числа
Для этого вопроса: «Задан массив, в котором каждый элемент встречается три раза, кроме одного, который встречается только один раз. Найдите элемент, который встречается один раз».
Я попробовал код, указанный на http://www.geeksforgeeks.org/find-the-element-that-appears-once/.
Но я получаю неправильный ответ 1, когда ввод 3,3,1,3,6,1,6,7,1.
Пожалуйста, помогите мне найти ошибку, которую я делаю.
#include<iostream>
using namespace std;
int getSingleOccurrence(int nArray[9], int n){
int ones = 0, twos=0;
int common_bit_mask=0;
for(int i=0;i<n;i++){
twos|= ones & nArray[i];
ones^=nArray[i];
common_bit_mask = ~(ones & twos);
ones&=common_bit_mask;
twos&=common_bit_mask;
}
return ones;
}int main(){
int nArray[]={3,3,1,3,6,1,6,7,1};
cout<<getSingleOccurrence(nArray,9);
return 0;
}
Решение
Это глупость, которая не имеет смысла в практическом коде. В этом случае алгоритм (явно) работает, только если все элементы присутствуют 3 раза, кроме одного, который присутствует один раз. Если какие-либо объекты присутствуют четное количество раз, это не удастся. В вашем входе 6 присутствует дважды, поэтому он терпит неудачу.
Другие решения
Это не работает, если у вас есть два из одного числа. А у вас два 6«S.
Также обратите внимание, что вы не должны указывать длину массива в параметре метода.
Это работает: ideone
#include <stdio.h>
int getSingleOccurrence(int nArray[], int n){ //note no array length here
int ones = 0, twos=0;
int common_bit_mask=0;
int i;
for(i=0;i<n;i++){
twos|= ones & nArray[i];
ones^=nArray[i];
common_bit_mask = ~(ones & twos);
ones&=common_bit_mask;
twos&=common_bit_mask;
}
return ones;
}int main(){
int nArray[]={3,3,1,3,6,1,6,7,1,6};
int result = getSingleOccurrence(nArray,10);
printf("Result %d", result);
return 0;
}