算法：数组中出现次数超过一半的数字

数据结构和算法

两种
(先排序，再去n/2下标较慢,O（nlogn）)

基于Partition的O(n)算法

如果排序后下标刚好是n/2，则是中位数，如果大于n/2则中位数在它左边，从左边数组找，否则到右边找

还要验证这个数组是不是真的超过一半

根据数组特点找出O(n)算法

遍历数组时保留两个值
一个是数组中的一个数字，一个是次数
当遍历到下一个数字的时候，如果和保存的数字相同，次数+1，如果不同-1，如果次数为0，我们需要保存下一个数字，并把次数设为1
最后要把次数设为1时对应的数字就是要找的

区别

第一种会修改输入的数组
如果不允许，只能用第二种