审题：
需要我们返回出现次数超过一半的元素的值
思路：
由于限制了空间复杂度为常数级别，所以哈希表或者额外创建数组的方式是无法通过的。
那么我们就使用双指针的方法。
首先我们需要进行排序，让数值相同的元素放在一起
left指针负责指向当前值的第一个位置，right负责寻找与当前值不同的下一个值的位置。
若找到不同的值就判断：
right-left>n/2则找到了出现一半以上的数据，把left索引的值存给answer
解题：
（1）预处理
（2）核心代码
在right进行搜索的时候会遇到三种情况
1.找到不同的值
2.没找到不同的值，但是还没搜索完
3.没找到不同的值，但是搜索完了
情况1：判断是否满足个数超过一半，满足就直接把值给answer。无论是否满足都要更新left索引
情况2：继续搜索
情况3：由于此时left和right指引的位置都是同一个数据，所以在判断数据个数的时候还要加个1
（3）特殊处理
当数据个数为1的时候，上述代码无法判断，所以我们直接让answer为该数据即可
数组中出现次数超过一半的数字_牛客题霸_牛客网
