【朱迪的LeetCode刷题笔记】169. Majority Element #Easy #Python
Given an array nums of size n, return the majority element.The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums =
Output: 3
Example 2:
Input: nums =
Output: 2
Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums <= 109
Follow-up:
Could you solve the problem in linear time and in O(1) space?
Judy
Python divide and conquerruntime beats 57.23% memory beats 8.57% taught by cs341
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List
:rtype: int
"""
h = len(nums) // 2
def f(lst):
l = len(lst)
m = l // 2
if l % 2 == 1 and nums.count(lst[-1]) > h:
return lst[-1]
if l == 1:
return lst
if l == 2:
if nums.count(lst) > h:
return lst
return lst
nlst = []
for i in range(0, m):
if lst == lst:
nlst.append(lst)
return f(nlst)
return f(nums)
Python boyer more majority vote algorithm runtime beats 65.21% memory beats 67.84% taught by sol
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List
:rtype: int
"""
x = 0
c = 0
for n in nums:
if c == 0:
x = n
c += 1
elif x == n:
c += 1
else:
c -= 1
return x
Sol1
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count = 0;
int candidate = 0;
for(int i = 0; i < nums.size(); i++){
if (count == 0){
candidate = nums;
}
if(nums == candidate){
count+=1;
}else {
count-=1;
}
}
return candidate;
}
};
页:
[1]