codility 之 OddOccurrencesInArray

题目描述（Task decription）:

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Assume that:

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

接替思路：

1. 由题目要求可知，元素个数为奇数个，只有一个元素是未配对的数；
2. 先将数组进行排序（使用泛型算法中的方法）；
3. 遍历数组，每次前进2个位置，如果第i位置与第i+1位置的元素不相等，则，第i位置的元素就是我们要求的数；

PS：感觉我的这个算法并不是很高级，在此抛砖引玉，期待大神的指点。

参考答案：

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    sort(A.begin(), A.end());
    
    unsigned i=0;
    for (; i<A.size()-1; i+=2)
    {
        if (A[i] != A[i+1])
        {
            break;
        }
    }
    
    return A[i];
}