题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度为 $9$ 的数组 ${ 1, 2, 3, 2, 2, 2, 5, 4, 2 }$。由于数字 $2$ 在数组中出现了 $5$ 次，超过数组长度的一半，因此输出 $2$。

如果这个数组是排好序的数组，那么我们很容易就可以统计出每个数字出现的次数，但是题目并没有说明数组是排序的，如果我们使用排序算法进行排序，它的时间复杂度为 $O(n\log n)$，但是这并不是最快的方法，下面介绍两种更快的解法。

如果我们将数组排好序，由于有一个数字的次数超过数组长度的一般，那么中位数一定是该数，即排好序的数组的 $n/2$ 的位置处就是我们需要输出的数字，换句话说，我们需要查找数组中第 $n/2$ 大的数字，对于查找第 $k$ 大的数字，我们可以通过 $partition$ 算法。

$partition$ 是快速排序用到的算法，它将数组分为两部分，前半部分的数小于后半部分的数，返回前半部分和后半部分分界处的下标 $index$($index$ 是前半部分的最后一个数的下标)，如果该下标为 $n/2$，那么找到了我们要输出的数，如果大于 $n/2$，那么数字在前半部分，我们对前半部分继续使用 $partition$ 算法；如果 $index$ 小于 $n / 2$，那么输出的数字在后半部分，我们对后半部分使用 $partition$ 算法。以此往复，直到 $index$ 的值为 $n/2$，我们就将该数输出。

代码如下

// partition 算法
private static int partition(int[] data, int start, int end) {
    if (end < start) {
        throw new RuntimeException("参数错误");
    }
    int num = data[end];
    int more = end + 1;
    int cur = start;
    while (cur < more) {
        if (data[cur] <= num) {
            cur++;
        } else {
            int number = data[cur];
            data[cur] = data[--more];
            data[more] = number;
        }
    }
    return cur - 1;
}

public static int findMoreThanHalfNumber(int[] data) {
    int start = 0;
    int end = data.length - 1;
    int index = partition(data, start, end);
    // middle 代表是 n /2 的位置
    int middle = start + (end - start) / 2;
    while (index != middle) {
        if (index < middle) {
            start = index + 1;
            index = partition(data, start, end);
        } else {
            end = index - 1;
            index = partition(data, start, end);
        }
    }
    return data[index];
}

下面讲解第二种解法，题目说有一个数字超过数组长度的一半，说明该数字出现的次数比其他数字出现的次数加起来都多，所以我们可以考虑在遍历数组时保存两个变量，一个保存的是数组中的数字，一个是次数；如果下一个数字与保存的数字不同，那么次数减一，如果相同，那么次数加一。如果次数已经为 $0$，那么设置保存的数字为目前的数字，因为输出的数字出现的次数比其他所有数字出现的次数加起来都多，所以最后保存的数字一定是我们想要输出的数字。

代码如下

public static int moreThanHalfNumber(int[] data) {
    if (data == null || data.length == 0) {
        throw new RuntimeException("参数操作");
    }
    // 保存次数
    int count = 1;
    // 保存数字
    int result = data[0];
    for (int i = 1; i < data.length; i++) {
        if (count == 0) {
            result = data[i];
            count = 1;
            continue;
        }
        if (result != data[i]) {
            count--;
        } else {
            count++;
        }       
    }
    return result;
}