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.

//解题思路：先排序，后对数组进行遍历
class Solution {
public:
	int majorityElement(vector<int>& nums) {
		int n = nums.size();
		if (n == 0) return nums[0];
		int c = 0;
		sort(nums.begin(), nums.end()); //对数组进行排序
		for (int i = 0; i < n;  )
		{
			for (int j = i; j < n; ++j)
			{
				if (nums[j] == nums[i])
					c++;
				else
				{
					i = j;
					continue;
				}
				if (c>n / 2)  return nums[j - 1];
				else
				{
					continue;
				}
			}
		}
	}
};