力扣169. 多数元素

Problem: 169. 多数元素

题目描述

思路

1.哈希表

将数组中的每个元素作为键，其出现的次数作为值存入哈希表中，最终找出多数元素

2.排序

将数组进行升序排序，由于多数元素大于数组长度的一半，则排序后的数组中的中间位置一定是多数元素

复杂度

思路1：
时间复杂度:

$O(n)$；其中$n$是数组nums的大小

空间复杂度:

$O(n)$

思路2：
时间复杂度:

$O(nlogn)$

空间复杂度:

$O(1)$

Code

思路1：

class Solution {
public:
	/// <summary>
	/// Gets the majority of the elements in the array
	/// </summary>
	/// 
	/// <param name="nums"> Given array </param>
	/// <returns> int </returns>
	int majorityElement(vector<int>& nums) {
		unordered_map<int, int> map;
		for (int i = 0; i < nums.size(); ++i) {
			if (map.find(nums[i]) != map.end()) {
				map[nums[i]] = 1;
			} else {
				map[nums[i]] = map[nums[i]] + 1;
			}
		}
		for (auto it = map.begin(); it != map.end(); ++it) {
			if (it->second > (nums.size() / 2)) {
				return it->first;
			}
		}
		return -1;
	}
};

思路2：

class Solution {
public:
	/// <summary>
	/// Gets the majority of the elements in the array
	/// </summary>
	/// 
	/// <param name="nums"> Given array </param>
	/// <returns> int </returns>
	int majorityElement(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		return nums[nums.size() / 2];
	}
};