169 Majority Element 求眾數(shù)
Description:
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:
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
題目描述:
給定一個大小為 n 的數(shù)組卖擅，找到其中的眾數(shù)漓踢。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素羊精。
你可以假設數(shù)組是非空的，并且給定的數(shù)組總是存在眾數(shù)瘪吏。
示例:
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
思路:
遍歷數(shù)組, 維護一個 count, 初始為0, 當 count為 0時, 將結(jié)果更新為當前元素, 結(jié)果與數(shù)組元素相等時, count++, 否則 count--, 由于眾數(shù)一定是大于 ? n/2 ? 的元素, 最后得到的結(jié)果元素的 count一定大于 0.
不能使用排序, 因為排序時間復雜度為O(nlgn)
時間復雜度O(n), 空間復雜度O(1)
代碼:
C++:
class Solution
{
public:
int majorityElement(vector<int>& nums)
{
int count = 0, result = 0;
for (int num : nums)
{
if (!count) result = num;
if (result == num) count++;
else count--;
}
return result;
}
};
Java:
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int result = 0;
for (int num : nums) {
if (count == 0) result = num;
if (result == num) count++;
else count--;
}
return result;
}
}
Python:
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]
