数组中出现次数超过一半的数字——剑指offer

这个解法参考了剑指offer，利用快排的partition函数思想，超过一半的数字肯定是数组的中位数，也就是下标为n/2的数字，我们每次随机找一个下标，然后逐步接近n/2.
还要注意vector的传参问题，partition是需要对vector进行排序的，所以要传入引用，并且用< algorithm >中自带的swap方法对vector的两个元素进行交换。

#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;

int partition(vector<int> &arr, int length, int start, int end)
{

    //在start和end之间取一个随机数
    int index = rand() % (end-start+1) + start;
    swap(arr[index], arr[end]);
    //end下标和数组所有数进行比较
    int i = 0;
    //samll总是小于end的最右一个元素下标
    int small = start -1;
    for (i = start; i < end; i++) {
        if (arr[i] < arr[end]) {
            ++small;
            if (small != i) {
                swap(arr[small], arr[i]);
            }
        }
    }
    ++small;

    swap(arr[small], arr[end]);

    return small;
}

bool checkMoreThanHalf(vector<int> arr, int length, int number) {
    int times = 0;
    for (int i = 0; i < length; i++) {
        if (arr[i] == number) {
            times++;
        }
    }
    if (times * 2 <= length)
    {
        return false;
    }
    return true;

}

int MoreThanHalfNum_Solution(vector<int> numbers) {
    int start = 0;
    int end = numbers.size() - 1;
    int middle = (end + start ) >> 1;
    int index = partition(numbers, numbers.size(), start, end);
    while (middle != index) {
        if (middle < index) {
            end = index -1;
            index = partition(numbers, numbers.size(), start, end);
        }
        else {
            start = index +1;
            index = partition(numbers, numbers.size(), start, end);
        }
    }
    if (!checkMoreThanHalf(numbers, numbers.size(), numbers[index]))
        return 0;
    return numbers[index];
}

int main()
{
    srand((unsigned int)time(NULL));
    int arr[] = { 1,2,3,2,4,2,5,2,3 };
    int length = sizeof(arr) / sizeof(arr[0]);
    //quick_sort(arr, length, 0, length-1);
    vector<int> array;
    for (int i = 0; i < length; i++) {
        array.push_back(arr[i]);
    }
    int ret = MoreThanHalfNum_Solution(array);
    printf("%d", ret);
    system("pause");
}