【朱迪的LeetCode刷题笔记】169. Majority Element #Easy #Python

Judie

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 = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

Follow-up:
Could you solve the problem in linear time and in O(1) space?

Judy
Python divide and conquer  runtime beats 57.23% memory beats 8.57% taught by cs341

1. class Solution(object):
   
2.     def majorityElement(self, nums):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :rtype: int
   
6.         """
   
7.         h = len(nums) // 2
   
8.         
   
9.         def f(lst):
   
10.             l = len(lst)  
    
11.             m = l // 2
    
12.             
    
13.             if l % 2 == 1 and nums.count(lst[-1]) > h:
    
14.                 return lst[-1]            
    
15.             
    
16.             if l == 1:
    
17.                 return lst[0]
    
18. 
    
19.             if l == 2:
    
20.                 if nums.count(lst[0]) > h:
    
21.                     return lst[0]
    
22.                 return lst[1]
    
23. 
    
24.             nlst = []
    
25.             
    
26.             for i in range(0, m):
    
27.                 if lst[i] == lst[i+m]:
    
28.                     nlst.append(lst[i])
    
29.             
    
30.             return f(nlst)
    
31.         
    
32.         return f(nums)

复制代码

Python boyer more majority vote algorithm runtime beats 65.21% memory beats 67.84% taught by sol

1. class Solution(object):
   
2.     def majorityElement(self, nums):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :rtype: int
   
6.         """
   
7.         
   
8.         x = 0
   
9.         c = 0
   
10. 
    
11.         for n in nums:
    
12.             if c == 0:
    
13.                 x = n
    
14.                 c += 1
    
15.             elif x == n:
    
16.                 c += 1
    
17.             else:
    
18.                 c -= 1
    
19.         
    
20.         return x

复制代码

Sol1

1. class Solution {
   
2. public:
   
3.     int majorityElement(vector<int>& nums) {
   
4.         int count = 0;
   
5.         int candidate = 0;
   
6. 
   
7.         for(int i = 0; i < nums.size(); i++){
   
8.             if (count == 0){
   
9.                 candidate = nums[i];
   
10.             }
    
11.             if(nums[i] == candidate){
    
12.                 count+=1;
    
13.             }else {
    
14.                 count-=1;
    
15.             }
    
16.         }
    
17.         return candidate;
    
18.     }
    
19. };

复制代码