当前位置：网站首页>Leetcode169 detailed explanation of most elements

Given a size of n Array of nums , Return most of the elements . Most elements refer to the number of occurrences in an array Greater than ⌊ n/2 ⌋ The elements of .

You can assume that the array is not empty , And there are always many elements in a given array .

The frequency of occurrence is greater than n/2, It indicates that the number of elements accounts for more than half of the whole array

Example

Example 1

 Input ：nums = [3,2,3]
 Output ：3

Example 2

 Input ：nums = [2,2,1,1,1,2,2]
 Output ：2

analysis

Sequencing

Since most elements account for more than half , Then sort the whole array , The elements in the middle of the array are most elements

Hashtable

Traversing the entire array from beginning to end , Record the number of occurrences of each number ,key For the elements ,value Is the number of occurrences ,value The largest elements are most elements

Code

Sequencing

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()  #  Sort 
        half = len(nums) // 2
        return nums[half]

HashTable

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        mapping = {}
        for num in nums:
            if num not in mapping:
                mapping[num] = 0
            mapping[num] = mapping.get(num)+1
        half = len(nums) // 2
        for key in mapping.keys():
            if mapping[key] > half:
                return key
        return -1

原网站

版权声明
本文为[Aries by]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/206/202207252355027710.html