169.多数元素

LeetCode LeetCode 数组哈希表热题100 排序分治计数

发布时间 : 2000-01-10 01:06

字数:1.4k 阅读 :

评论:

169.多数元素

169.多数元素

169.1 题目

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

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

提示：

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

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

169.2 题解

方法一：哈希表统计

思路

最直观的方法：用字典统计每个元素出现的次数，然后找出出现次数超过 n/2 的那个。

题目保证多数元素一定存在，所以不需要处理不存在的情况。

举个例子：nums = [2,2,1,1,1,2,2]

统计：{2:4, 1:3}
n=7，n/2=3
2出现4次 > 3，返回2

复杂度分析

时间复杂度：O(n)，遍历一次数组
空间复杂度：O(n)，字典存储所有元素

代码

// 方法一：哈希表统计
static int MajorityElement1(int[] nums)
{
    Dictionary<int, int> countDict = new Dictionary<int, int>();

    foreach (var num in nums)
    {
        if (countDict.ContainsKey(num))
            countDict[num]++;
        else
            countDict[num] = 1;

        if (countDict[num] > nums.Length / 2)
            return num;
    }

    return -1;
}

方法二：摩尔投票法

思路

一个很巧妙的方法：把多数元素看作”候选人”，其他元素看作”反对票”。因为多数元素超过一半，所以最终一定会”胜出”。

具体做法：

维护一个候选元素和计数器
遇到相同元素，计数器+1
遇到不同元素，计数器-1
计数器归零时，更换候选元素

为什么这样是对的？因为多数元素超过一半，即使所有其他元素都”反对”，多数元素还是会剩下来。

举个例子：nums = [2,2,1,1,1,2,2]

candidate=2, count=1
遇到2：count=2
遇到1：count=1
遇到1：count=0，更换candidate
遇到1：candidate=1, count=1
遇到2：count=0，更换candidate
遇到2：candidate=2, count=1
返回2

复杂度分析

时间复杂度：O(n)，遍历一次数组
空间复杂度：O(1)，只使用两个变量

代码

// 方法二：摩尔投票法
static int MajorityElement2(int[] nums)
{
    int candidate = nums[0];
    int count = 1;

    for (int i = 1; i < nums.Length; i++)
    {
        if (nums[i] == candidate)
        {
            count++;
        }
        else
        {
            count--;
            if (count == 0)
            {
                candidate = nums[i];
                count = 1;
            }
        }
    }

    return candidate;
}

169.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个大小为 n 的数组 nums ，返回其中的多数元素。
        // 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        // 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

        // 示例 1：
        // 输入：nums = [3,2,3]
        // 输出：3

        // 示例 2：
        // 输入：nums = [2,2,1,1,1,2,2]
        // 输出：2

        // 提示：
        // n == nums.length
        // 1 <= n <= 5 * 104
        // -109 <= nums[i] <= 109

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

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 3, 2, 3 };
        int result1 = MajorityElement1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = MajorityElement2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 2, 2, 1, 1, 1, 2, 2 };
        int result2 = MajorityElement1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = MajorityElement2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：字典统计元素出现次数
    static int MajorityElement1(int[] nums)
    {
        // 创建一个哈希表，用于存储每个元素的出现次数
        Dictionary<int, int> countDict = new Dictionary<int, int>();

        // 遍历数组中的每个元素
        foreach (var num in nums)
        {
            // 如果哈希表中已包含当前元素，增加其出现次数
            if (countDict.ContainsKey(num))
            {
                countDict[num]++;
            }
            else
            {
                // 如果哈希表中不包含当前元素，将其添加到哈希表中，出现次数初始化为1
                countDict[num] = 1;
            }

            // 检查当前元素的出现次数是否超过数组长度的一半
            if (countDict[num] > nums.Length / 2)
            {
                // 如果是，则该元素为多数元素，直接返回该元素
                return num;
            }
        }

        // 此题假设数组总是存在多数元素，因此不会执行到这里
        return -1;
    }

    // 方法二：摩尔投票法
    // 初始化候选元素和出现次数，遍历数组，如果和候选元素相同就加出现次数，不同就减出现次数，出现次数减为0重置候选元素
    static int MajorityElement2(int[] nums)
    {
        // 初始化候选元素为数组的第一个元素
        int candidate = nums[0];
        
        // 初始化候选元素的出现次数为1
        int count = 1;

        // 从数组的第二个元素开始遍历
        for (int i = 1; i < nums.Length; i++)
        {
            // 如果当前元素与候选元素相同，增加候选元素的出现次数
            if (nums[i] == candidate)
            {
                count++;
            }
            else
            {
                // 如果当前元素与候选元素不同，减少候选元素的出现次数
                count--;

                // 如果候选元素的出现次数变为0，更新候选元素为当前元素，并重置出现次数为1
                if (count == 0)
                {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }

        // 最终的候选元素即为多数元素
        return candidate;
    }



    #endregion
}

169.4 运行结果

示例1 方法1 输出：3
示例1 方法2 输出：3
示例2 方法1 输出：2
示例2 方法2 输出：2

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com