5/16每日一題(返回出像次數最多的元素,不使用額外空間)

 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?

class Solution:

    def majorityElement(self, nums: List[int]) -> int:

        nums.sort() #排序

        #合理推斷中位數就是多數的元素

        mid=len(nums)//2

        return nums[mid]

--------------------------------------------

參考解答

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return Counter(nums).most_common()[0][0]  

#他使用Coumter()把nums列表轉換成字典(元素:次數)

#most_common()會回傳一個列表 [ (最多元素,最多元素的次數) , (次多元素,次多元素次數) , ......]

#p.s  Counter()這個類別 要使用 from collections import Counter

----------------------------------------

import statistics
f = open("user.out", 'w')
for line in stdin:
    l = sorted(map(int, line.rstrip()[1:-1].split(',')))
    print(l[len(l) // 2], file=f)
exit(0)

#大神
-------------------------------------