算法之寻找数组中的多数元素

题目

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

初步分析

首先，我们先按照一般思路想。可以新定义一个数组来存储原始数组中每个不同元素出现的个数，然后定义两个变量来存储当前最大出现的次数和当前的多数元素。

初步实现代码

private double FindNum(double[] originArr)
{
    int[] tempArr = new int[originArr.Length];
    int maxCount = 1;
    double maxValue = originArr[0];

    for (int i = 0; i < originArr.Length; i++)
    {
        tempArr[i] = 1;
        for (int j = i + 1; j < originArr.Length; j++)
        {
            if (originArr[j] == originArr[i])
            {
                tempArr[i]++;
                if (maxCount < tempArr[i])
                {
                    maxCount = tempArr[i];
                    maxValue = originArr[i];
                }
            }
        }
    }

    return maxValue;
}

简单解释下这个函数，首先我们这个函数接收原始的数组，然后新定义一个整型数组。新数组的最大长度最多也就是原始数组每个元素都不同的情况，不过根据题中描述，多数元素一定存在，那么理论上这个数组的最大长度也就是n/2。简单解释下，长度为n数组多数元素必定占n/2+1以上个，其它元素即使都不同最多也就占n/2-1个，加上那个多数元素最长为n/2即可。不过这里我们并不能这样定义，往后看即知。
maxCount变量代表数组中元素最大出现的次数，初始值为1，maxValue变量代表数组中的多数元素。
这里有个细节，由于存放元素出现次数的数组与原始数组唯一的对应关系就是下标，所以我们存的某一个元素的出现次数在tempArr里是不连续的。比如原始数组为1,1,2,2,2,那么当这段程序执行后，tempArr[0]的值为2，代表1出现了两次，tempArr[1]的值为原始值1，tempArr[2]的值为3，代表2出现了3次，tempArr[3]、tempArr[4]的值都为原始值1。这也是为什么不能把tempArr数组长度定义为n/2的原因。

验证

这里我们新建一个WPF程序，然后在MainWindow.xaml里简单布下局，一个文本框用于输入内容，一个按钮用来给寻找多数元素的函数创造调用时机，多数元素通过后台调用弹窗显示即可。
布局代码：

<Window x:Class="FindMostElement.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:FindMostElement"
        mc:Ignorable="d"
        Title="MainWindow" Height="450" Width="800">
    <Grid>
        <StackPanel HorizontalAlignment="Center" VerticalAlignment="Center" Orientation="Horizontal">
            <TextBox x:Name="txt_Arr" Width="200" Height="100" TextWrapping="Wrap" VerticalScrollBarVisibility="Auto"></TextBox>
            <Button x:Name="btn_Start" Margin="10,0,0,0" Width="80" Height="30" Click="btn_Start_Click">开始</Button>
        </StackPanel>
    </Grid>
</Window>

我们这里把MainWindow.xaml.cs的代码也一起贴出来，方便读者自行去验证~

using System;
using System.Windows;

namespace FindMostElement
{
    /// <summary>
    /// MainWindow.xaml 的交互逻辑
    /// </summary>
    public partial class MainWindow : Window
    {
        /// <summary>
        /// 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
        /// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        /// </summary>

        public MainWindow()
        {
            InitializeComponent();
            txt_Arr.Text = "3,2,3";
        }

        private void btn_Start_Click(object sender, RoutedEventArgs e)
        {
            string[] strOriginArr = null;
            double[] originArr = null;

            try
            {
                strOriginArr = txt_Arr.Text.ToString().Split(',');
                originArr = new double[strOriginArr.Length];
                for (int i = 0; i < strOriginArr.Length; i++)
                {
                    originArr[i] = int.Parse(strOriginArr[i]);
                }
            }
            catch (Exception ex)
            {
                MessageBox.Show("请输入正确的数组元素，元素中间以“,”分隔！\n\r" + ex.Message, "警告", MessageBoxButton.OK, MessageBoxImage.Warning);
                return;
            }

            double mostValue = FindNum(originArr);
            MessageBox.Show("该数组中的多数元素为：" + mostValue + "。", "信息", MessageBoxButton.OK, MessageBoxImage.Information);
        }

        private double FindNum(double[] originArr)
        {
            int[] tempArr = new int[originArr.Length];
            int maxCount = 1;
            double maxValue = originArr[0];

            for (int i = 0; i < originArr.Length; i++)
            {
                tempArr[i] = 1;
                for (int j = i + 1; j < originArr.Length; j++)
                {
                    if (originArr[j] == originArr[i])
                    {
                        tempArr[i]++;
                        if(maxCount < tempArr[i])
                        {
                            maxCount = tempArr[i];
                            maxValue = originArr[i];
                        }
                    }
                }
            }

            return maxValue;
        }
    }
}

思考

到这里，我们的一般处理相当于完成了。这时我们应该会想到，既然是算法题，那么理论上必定会有更优的解法。我们可以这样想，对于用程序做一件事情来说，我们要着重关注起始条件和最终要出的结果，要善于发现起始条件中隐含的信息。拿此题来讲，我们的起始条件是一个必定存在多数元素的数组，然后要的结果就是输出多数元素。我们如果想要更优，那么就需要去掉刚才那个方法的一些过程，比如记录每个元素出现次数的数组，记录当前最大出现次数和当前多数元素值的变量。

更优的解法

好了，话不多说，更优的一个解法如下。首先我们假定多数元素为原始数组第一个元素，定义变量mostValue，然后我们遍历数组，遇到和假定的元素一样的就+1，不一样的就-1，最后结果必然是一个大于0的值。然后我们用一个中间变量curSum来表示当前总和，每次当curSum等于0时，把当前遍历到的数组元素值赋给mostValue，当遍历结束后，mostValue就是我们要找的多数元素值。

private double FastFindNum(double[] originArr)
{
    double mostValue = originArr[0];
    int curSum = 0;

    foreach (double tempValue in originArr)
    {
        if (curSum == 0) mostValue = tempValue;
        curSum += (mostValue == tempValue ? 1 : -1);
    }

    return mostValue;
}

理解后，建议大家自行去验证其正确性。