169.多数元素

一、题述

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于  [n/2]  的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入:[3,2,3]
输出:3


示例 2:

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

进阶

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

二、题解

1、方法一:排序法

由题意知,我们需要提取出出现次数大于总数一半的“众数”,由数学原理易得,排序后[n/2]处的数必为我们所需要的那个数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

复杂度分析

时间复杂度:数组排序的时间复杂度为O(nlogn)

空间复杂度:O(logn)

2、方法二:哈希表

我们可以采用类似于Python中键值对的方法,对数组进行遍历,收集所有的元素以及他们出现的次数。我们也可以用类似于擂台的办法,保留出现次数最多的数字,以此避免对整个数组的遍历。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) { 
/**
迭代器遍历
,类似于如下代码:
for(int i=0;i<arr.length;i++){
int num = arr[i];
...
}
**/
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

复杂度分析

  • 时间复杂度:O(n), n 是数组 nums 的长度.
  • 空间复杂度:O(n).

3、方法三:Boyer-Moore 投票算法(Leetcode解法)

有一说一,没太看明白emmm

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇