Leetcode#169. Majority Element

本文主要是介绍Leetcode#169. Majority Element，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：一个非空数组，里面有元素出现了数组长度一半以上，返回这个元素

解题思路： 最容易想的是排序，返回中间那个元素即可，时间复杂度O(nlog(n))，空间复杂度O(l)；另一种思路借助于哈希表，遍历数组每一个元素，出现次数记录在hash表中，若hash值超过了数组长度的一半，返回这个元素即可，时间复杂度O(n)，空间复杂度O(n)。

C++实现如下：

解法一：排序

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(),nums.end());return (nums[nums.size()/2]);}
};

解法二：利用一个hash

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

这篇关于Leetcode#169. Majority Element的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---