I am looking for an algorithm to solve the following problem: Given an integer array of size n, find one (arbitrary) element of this array which occurs exactly once. All numbers which do not fit this requirement occur an even number of times in the array. If the array does not contain any such number, the result is irrelevant.
An example would be the input [1, 2, 2, 4, 4, 2, 2, 3] with both 1 and 3 being a correct output.
Most importantly, the algorithm should run in O(n) time and require only O(1) additional space. I have been told that this is possible but could not come up with a solution myself.
via Chebli Mohamed
Aucun commentaire:
Enregistrer un commentaire