=====
题目描述如下:
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
=====
算法思路:
题目中提到给定的数组中总是存在多数元素，即，大于n/2。我们设这个元素为res。我们想象一下，假如我们把原数组排成两行。第一行是所有的res元素。第二行是非res元素。那么第一行至少比第二行多一个。如果我们只要碰到一对儿元素不同，我们就删除它，最后把所有不同的元素对儿都删除，那么剩下那些元素的就是这个res元素。咱简单证明一下:
1. 剩下的元素都是相同的，因为所有不同的都已经删除。
2. 如果剩下的元素不是res，那res的那些元素都已经被删除了，每个res元素必然能找到一个与它不同的元素e。那这些元素e的数量至少是n/2+1。这显然与题设相矛盾，此题得证。
基于这个思想，我们可以有如下的算法:
我们设两个变量p1=0，p2=1，然后移动p2从左往右遍历原数组。每访问一个元素，我们做如下操作:
1. 如果nums[p1]==nums[p2]，由于两个元素相同，我们把p1向右移动一格，表示p1前面的元素都是相同的。我们用最新位置的p1继续与p2比较。这里有两点需要说明一下:
(1) 由于有可能p2与p1不相邻，所以我们需要把p2处的元素，放到移动后的p1处，为了做进一步的比较。
(2) 由于p2先于p1访问到后面的元素，因此移动后的p1所在的元素已经没用，我们可以直接赋值，nums[p1]=nums[p2]。
2. 如果nums[p1]!=nums[p2]，此时的p1，p2的元素已经没用，我们把p1向左移动一格。继续和p2比较。
3. 如果nums[p1]!=nums[p2] 且 p1此时为0。那么我们把p2的下一个位置的值放到nums[0] 处。
此算法保证了p1最终指向的就是那个多数元素。
算法的时间复杂度为O(n)，空间复杂度为O(1)。下面是Python代码实现:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
p1=0
p2=1
n=len(nums)
while p2<n:
if nums[p1]==nums[p2]:
p1+=1
nums[p1]=nums[p2]
elif p1==0:
p2+=1
nums[p1]=nums[p2]
else:
p1-=1
p2+=1
return nums[p1]