剑指 Offer 39. 数组中出现次数超过一半的数字
2021/5/22 10:25:14
本文主要是介绍剑指 Offer 39. 数组中出现次数超过一半的数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
限制:
1 <= 数组长度 <= 50000
注意:本题与主站 169 题相同:https://leetcode-cn.com/problems/majority-element/
思路
golang
寻找主元素
(即数组中存在某一个元素的数量超过数组长度的半数)
这里题目说了不需要考虑数组为空的情况,也不需要考虑不存在主元素主要解法:
- 对当前数组排序后,主元素必定在len(nums)/2的位置
时间复杂度:考虑到快速排序最快也需要O(nlogn) 空间复杂度:O(1)- hash表法,利用hash表统计数组中元素出现的次数,如果超过数组长度的一半,即为主元素
时间复杂度:需要遍历数组所以为O(n) 空间复杂度:需要建立一个辅助数组为O(n)- 摩尔投票法,利用不同元素次数正负抵消的思想,如果相邻的元素相同,统计次数count+1,如果不同count-1,最后count次数大于0的那个元素就是主元素
时间复杂度:需要遍历数组所以为O(n) 空间复杂度:O(1)
// 1.数组排序法 func majorityElement(nums []int) int { sort.Ints(nums) return nums[len(nums)/2] }
// 2.hash表法 func majorityElement(nums []int) int { mp := make(map[int]int, len(nums)) var res int for i := 0; i < len(nums); i++ { // 以数组的值作为key,统计出现的次数 mp[nums[i]]++ if mp[nums[i]] > len(nums)/2 { res = nums[i] } } return res }
// 3.摩尔投票法 func majorityElement(nums []int) int { tmp, count := 0, 0 for i := 0; i < len(nums); i++ { if count == 0 { tmp = nums[i] count++ } else { if tmp == nums[i] { count++ } else { count-- } } } return tmp }
这篇关于剑指 Offer 39. 数组中出现次数超过一半的数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt