Java – find unpaired numbers in an array

I have an array that repeats all elements except one:

int[] a={2,6,2,4,1,4};

How do I find unpaired element integers?

Solution

You can do the following:

>Method 1 – o (n log n): sort the array Then, the elements of the array are sorted iteratively, two at a time (I = 0, I = 2, etc.) When [i] and [I 1] are not equal – or when I 1 = = a.length – you know that a [i] is not paired. > Method 2 – o (N2): iterate elements For each element a [i], iterate over the element (in a nested loop) and see if a [i] = = a [J] and I= j. If not, [i] is not paired. > Method 3 – o (m), where m is the difference between the maximum and minimum elements (note that M is Ω (n)): iterate the elements, find the maximum and minimum values min and max. create an int [] B = New Int [max-min 1] Iterate over the elements again, incrementing B [a [i] - min] for each element Then iteration B; When you find that B [J] = = 1, j is unpaired

Note: you use the term "element integer", but this is not a real term The above assumes that you mean "integer value element" If you actually mean "element index", you can only use method 2 without modification Method 3 requires some adjustments and method 1 requires a lot of adjustments (of course, once you find a value that appears only once, you can traverse the array again to find the index of the value - provided you still have the original array order.)

Edit add: I don't know how I missed it before - I don't think I'm used to bitwise arithmetic when writing Java - but the best solution is actually:

>Method 4 – o (n): computes bitwise - XOR, ^. For all elements of the array This is an unpaired element You see, XOR is exchangeable and associative, so 2 ^ 6 ^ 6 ^ 2 ^ 4 ^ 1 ^ 4 is the same as 1 ^ (2 ^ 2) ^ (4 ^ 4) ^ (6 ^ 6); And x ^ x is always 0, so other outputs are always cancelled You can write:

int result = 0;
for(int i : a)
    result ^= i;

Calculates unpaired elements (to get the index of unpaired elements, you need to traverse the array again to find the result.)