Я пытаюсь ответить на следующий вопрос: у вас есть массив целых чисел, так что каждое целое число содержит нечетное количество раз, кроме 3 из них. Найдите три числа.
до сих пор я пришел с методом грубой силы:
public static void main(String[] args) {
// TODO Auto-generated method stub
int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };
FindEvenOccurance findEven = new FindEvenOccurance();
findEven.getEvenDuplicates(number);
}
// Brute force
private void getEvenDuplicates(int[] number) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : number) {
if (map.containsKey(i)) {
// a XOR a XOR a ---- - -- - - odd times = a
// a XOR a ---- -- -- --- - even times = 0
int value = map.get(i) ^ i;
map.put(i,value);
} else {
map.put(i, i);
}
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 0) {
System.out.println(entry.getKey());
}
}
}
Он отлично работает, но не эффективен.
O/p:
1
5
6
8
Но вопросы указывают, что нам нужно сделать это в O (1) пространстве и O (N) временной сложности. Для моего решения временной сложностью является O (N), но пространство также O (N). Может ли кто-нибудь предложить мне лучший способ сделать это с помощью O (1) пространства?
Спасибо.
