温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

leetCode 169. Majority Element 数组

发布时间:2020-07-12 13:15:12 来源:网络 阅读:326 作者:313119992 栏目:编程语言

169. 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.


思路1:

使用map来处理。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
    	map<int, int> record;
    	for (int i = 0; i < nums.size(); i++)
    	{
    		if (record.find(nums[i]) == record.end())
    		{
    			record.insert(pair<int, int>(nums[i], 1));
    			if (record[nums[i]] > nums.size() / 2)
    			{
    				return nums[i];
    			}
    		}
    		else
    		{
    			record[nums[i]] += 1;
    			if (record[nums[i]] > nums.size() / 2)
    			{
    				return nums[i];
    			}
    		}
    	}
    	return 0;
    }
};

思路2:

采用双循环

int majorityElement(vector<int>& nums) {
	int hit = 0;
	int currentElem;
	for (int i = 0; i < nums.size(); i++)
	{
		currentElem = nums[i];
		hit = 0;
		for (int j = 0; j < nums.size(); j++)
		{
			if (nums[j] == currentElem)
			{
				hit++;
				if (hit > nums.size() / 2)
				{
					return currentElem;
				}
			}
		}
	}
	return 0;
}


2016-08-10 12:19:37

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI