【5分钟力扣】面试题 17.10. 主要元素

文章目录

一、前言二、题目三、解法和思路思路1思路2

一、前言

事实上，成功仅代表了你工作的1%，成功是99%失败的结果。

每天五分钟，看懂一道简单、中等难度的算法题，尽可能将复杂的题讲清楚。

疯狂学习python中，2020-09-04更新

二、题目

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5] 输出：5

示例 2：

输入：[3,2] 输出：-1

示例 3：

输入：[2,2,1,1,1,2,2] 输出：2

说明： 你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-majority-element-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

三、解法和思路

思路1

将数组从小到大进行排序，循环遍历，如果满足 nums[i] == nums[i + halflen]，则说明数组中有占比超过一半的元素。

复杂度分析：

时间复杂度：O(N) 空间复杂度：O(1)

nums = [1,2,5,9,5,9,5,5,5] class Solution: def majorityElement(self, nums: List[int]) -> int: number = int(len(nums)/2) # 排序 nums.sort() for i in range(len(nums)-number): if nums[i] == nums[i+number]: return nums[i] return -1 if __name__ == '__main__': obj = Solution() obj.majorityElement(nums)

思路2

使用Counter方法对数组进行计数，返回一个字典类型的数据,键是元素，值是元素出现的次数，用值和halflen进行比较

复杂度分析：

时间复杂度：O(N) 空间复杂度：O(1)

from typing import List nums = [2,2,1,1,1,2,2] class Solution: def majorityElement(self, nums: List[int]) -> int: number = int(len(nums)/2) from collections import Counter a = Counter(nums) for i in a: if a[i] > number: return i return -1 if __name__ == '__main__': obj = Solution() print(obj.majorityElement(nums))