spriteYang
1/3/2019 - 7:29 AM

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.

.cpp
content_copyfile_download
int majorityElement(vector<int>& nums) {
	int len = nums.size();
	int standard = len / 2;
	vector<vector<int>> arr(len);//定义一个二维数组，有len行
	for (int i = 0; i < len; i++)//定义每一行有2列
		arr[i].resize(2);	
	arr[0][0] = nums[0];
	arr[0][1] = 1;
	int k = 1;//计数器
	for (int i = 1; i < len; i++) //用来读取nums的数据
	{
		for (int j = 0; j < k; j++)
		{
			if (nums[i] == arr[j][0])
				arr[j][1]++;
			else if(j==k-1)
			{
				arr[k][0] = nums[i];
				arr[k++][1]++;
			}
		}
		nums[i] = 0;
	}
	int j = 0;
	for (int i = 0; i < k; i++)
	{
		if (arr[i][1]-1 >= standard)
		{
			nums.push_back(arr[i][0]);
			j = arr[i][1]-1;
			break;
		}
		else if(i==k-1)
			return 0;
	}
	return j;
}