169.多数元素

LeetCode LeetCode 数组哈希表分治排序计数

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

字数:1.3k 阅读 :

评论:

169.多数元素

169.多数元素

169.1 题目

知识点内容

169.2 题解

字典统计元素出现次数

// 方法一：字典统计元素出现次数
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;
}

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