题目地址：
https://oj.leetcode.com/problems/majority-element/
题目内容：
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
方法：
要求有两个：
0、时间复杂度是O(N)
1、空间复杂度是O(1) // 这个是当然的，否则来一个hashmap，谁不会 = _ =!
要点是维护这么一个性质：
首先，不妨假设目标元素出现了a次，而总共有b个元素，那么：
1>= b/a >= 1/2
我们可以设定两个指针，一个指向头部，一个指向尾部。要点在于维护这么一个性质：首尾指针之间的数组，目标元素数量占全部数量的1/2下取整之上。如果两个指针指向的元素不相等，说明此时至少有一个指针指向的元素不是所要求的元素，因此，我们可以抛弃这两个元素，这个时候目标元素在源数组中的比率不会降低。
证明就比较简单了。假设最坏的情况，有一个是目标元素，另一个不是，则有：
b/a < (b-1)/(a-2)，当2b >= a时成立。而2b >= a是题目给出的条件。
那么如果两个元素相等呢？我们还能抛弃这两个元素吗？回答是不能。因为(b-1)/(a-1) < b/a，不能维持目标元素在原数组中比率不降低的性质。
那该怎么办？答案是维护一个指向当前元素【下一个不相等】的指针，如果相等，那么和下一个和自己不相等的元素交换位置即可。这个指向下一个不相等的指针只会往前走，因此，最多走n次。而我们总共维护4个指针，最多O(4n)，还是O(n)。
下面是具体代码：
class Solution {
public:
int majorityElement(vector<int> &num) {
int start = ;
int fin = num.size() - ;
int startnxt = findNextStart(start,num,start); //找到下一个和start不等的指针。
int finnxt = findNextFin(fin,num,fin);
while (start < fin)
{
if (num[start] == num[fin])
{
if (startnxt >= finnxt) // 若当前首尾指针指向的数据相等，那么下轮操作后之间的数据就全部相等了，故可以直接返回结果。
return num[start];
swap(&num[start],&num[startnxt]);
}
start ++;
fin --;
startnxt = findNextStart(start,num,startnxt);
finnxt = findNextFin(fin,num,finnxt);
}
return num[start];
} int findNextStart(int start,vector<int> &num,int preptr)
{
int nowNumber = num[start];
int nxtPtr = preptr == start ? start + : preptr; // 若prestart正好为start，那么前进一格。否则在既有基础上出发。
while (nxtPtr < num.size() && num[start] == num[nxtPtr])
nxtPtr ++;
return nxtPtr;
} int findNextFin(int fin,vector<int> &num,int preptr)
{
int nowNumber = num[fin];
int nxtPtr = preptr == fin ? fin - : preptr;
while (nxtPtr >= && num[fin] == num[nxtPtr])
nxtPtr --;
return nxtPtr;
} void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
};
