左神算法 在数组中找到出现次数大于1/2的数

一、参考剑指offer的思路
如果数组中出现大于1/2的数，如果按顺序排列，这个数肯定出现在下标为N/2的数上，所以这里参考Top-K问题，用快速排序原理求得第N/2大的值，然后判断该值的数量有没有大于数组长度的一半。如果确认大于1/2，证明就是该数，如果不是，证明没有这样的数。代码如下

二、左神的思路
如果有个数出现次数大于1/2，此时遍历数组，删除两两不同的数，该数肯定出现在剩下的数中。因为极端情况，也是所有其他的数和该数拼掉，剩一个数，或者其他数自己拼掉，剩好几个该数。
但是反过来，剩下的数不一定能保证大于1/2，比如 1 2 1一定会剩下1，1 2 3剩下3就不是大于1/2的。所以还要做验证，这和思路一是一样的。

这问题的引申是【在数组中找到出现次数大于N/K的数】

public class Problem_06_FindKMajority {

    public static void printHalfMajor(int[] arr) {
        int cand = 0;
        int times = 0;
        for (int i = 0; i != arr.length; i++) {
            if (times == 0) {
                cand = arr[i];
                times = 1;
            } else if (arr[i] == cand) {
                times++;
            } else {
                times--;
            }
        }
        times = 0;
        for (int i = 0; i != arr.length; i++) {
            if (arr[i] == cand) {
                times++;
            }
        }
        if (times > arr.length / 2) {
            System.out.println(cand);
        } else {
            System.out.println("no such number.");
        }
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 1, 1, 2, 1 };
        printHalfMajor(arr);
    }

}