题目描述：

寻找异常数字。 输入一个无序的公差为1的等差数列，其中有一个数不属于此数列，找到这个数。

举例： 输入1 3 2 3 ， 输出为3 输入2 5 3 7 4，输出7

解法1：暴力解法

通过从头到尾遍历数组，找到异常的数字。

int GetExceptionalNumber(int arr[], int n)
{
    if (arr == nullptr || n < 3)
    {
        return -1;
    }
​
    QuickSort(arr, n);
​
    for (int i = 1; i < n; ++i)
    {
        if (arr[i] - arr[i-1] == 1)
        {
            continue;
        }
​
        if (i < n-1)
        {
            if (arr[i+1] - arr[i] == 1)
            {
                return arr[i-1];
            }
            else
            {
                return arr[i];
            }
        }
        else // (i-1) != 0
        {
            if (arr[i-1] - arr[i-2] == 1)
            {
                return arr[i];
            }
            else
            {
                return arr[i-1];
            }
        }
​
    }
​
    return -1; // not found
}

解法二：二分法

使用二分查找的方法，这里的关键是怎么确定目标数字。这里有两个关键点：1.数组的公差为1 ；2.排序后，数组是有序的。 如此，可通过判断数字与数字的下标是否相等。

int GetExceptionalNumber(int arr[], int n)
{
    if (arr == nullptr || n < 3)
    {
        return -1;
    }
​
    QuickSort(arr, n);
​
    // 判断第一个为异常数
    if (arr[1] - arr[0] != 1)
    {
        if (arr[2] - arr[1] == 1)
        {
            return arr[0];
        }
    }
​
    int startNumber = arr[0];
    int l = 0;
    int r = n - 1;
    while (l <= r)
    {
        int midIndex = l + (r-l)/2;
        if (l == r)
        {
            return arr[midIndex];
        }
​
        int midNumber = midIndex+startNumber;
        if (midNumber > arr[midIndex])
        {
            r = midIndex-1;
        }
        else // midNumber == arr[midIndex]
        {
            if (midIndex < n-1 && arr[midIndex+1] == arr[midIndex])
            {
                return arr[midIndex];
            }
            else if (midIndex > 0 && arr[midIndex-1] == arr[midIndex])
            {
                return arr[midIndex];
            }
            else
            {
                l = midIndex+1;
            }   
        }
    }
​
    return -1; // not found
}

代码中用到的快速排序：

​
template <typename T>
void swap(T* lhs, T* rhs)
{
    T temp = *lhs;
    *lhs = *rhs;
    *rhs = temp;
}
​
template <typename T>
int partition(T arr[], int l, int r)
{
    int mid = l + (r-l)/2;
    int randIdx = std::rand()%(r-l+1)+l;
    swap(&arr[l], &arr[randIdx]);
    T v = arr[l];
    int j = l;
    for (int i = l+1; i <= r; i++)
    {
        if (arr[i] < v)
        {
            j++;
            swap(&arr[i], &arr[j]);
        }
    }
​
    swap(&arr[l], &arr[j]);
    return j;
}
​
template <typename T>
void __QuickSort(T arr[], int l, int r)
{
    if (l >= r)
    {
        return;
    }
​
    int q = partition(arr, l, r);
    __QuickSort(arr, l, q);
    __QuickSort(arr, q+1, r);
​
}
​
template <typename T>
void QuickSort(T arr[], int n)
{
    if (arr == nullptr || n < 0)
    {
        return;
    }
​
    __QuickSort(arr, 0, n-1);
}