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.

Example 1:

Input: [3,2,3] Output: 3

Example 2:

Input: [2,2,1,1,1,2,2] Output: 2

給一個大小為n的數組，找出它的多數元素。數組非空，多數元素存在。多數元素：出現次數超過n/2的元素(超過數組長度一半)。

解法1: 用兩個循環跟蹤統計最多次數的元素。 T：O(n*n)? S: O(1)

解法2: BST,??T：O(nlogn)? S: O(n)

解法3：Boyer-Moore多數投票算法?Boyer–Moore majority vote algorithm，T：O(n)? S: O(1)

解法4: HashMap，?T：O(n)? S: O(n)

Java:

public class Solution {public int majorityElement(int[] num) {int major=num[0], count = 1;for(int i=1; i<num.length;i++){if(count==0){count++;major=num[i];}else if(major==num[i]){count++;}else count--;}return major;} }　　

Java：

public class Solution {public int majorityElement(int[] nums) {int res = 0, cnt = 0;for (int num : nums) {if (cnt == 0) {res = num; ++cnt;}else if (num == res) ++cnt;else --cnt;}return res;} }　　

Python: T: O(n), S: O(1)

class Solution:def majorityElement(self, nums):idx, cnt = 0, 1for i in xrange(1, len(nums)):if nums[idx] == nums[i]:cnt += 1else:cnt -= 1if cnt == 0:idx = icnt = 1return nums[idx]

C++:

class Solution { public:int majorityElement(vector<int>& nums) {int ans = nums[0], cnt = 1;for (const auto& i : nums) {if (i == ans) {++cnt;} else {--cnt;if (cnt == 0) {ans = i;cnt = 1;}}}return ans; } };

?

類似題目：

[LeetCode] 229. Majority Element II? 多數元素 II

?

All LeetCode Questions List 題目匯總

　　

　　

?

?

?

轉載于:https://www.cnblogs.com/lightwindy/p/8606860.html

總結

以上是生活随笔為你收集整理的[LeetCode] 169. Majority Element 多数元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。