【面试题】剑指offer29--数组中出现次数超过一半的数字

桃扇骨 2022-06-12 02:06 113阅读 0赞

问题是这样的：

![Center][]

对于这个问题我们首先想到的是，将数组进行排序，那么排序完了之后的数组中间的数字就是出现次数超过一半的数字，也就是中位数。

任意找一个数字，比这个数字小的都放在左边，比这个数字大的都放在右边。

如果选中的这个数字下标刚好是n/2,则这个数字就是中位数；

如果它的下标大于n/2，则中位数应该位于它的左边，接着在左边的数组里面查找；

如果它的下标小于n/2，则中位数应该位于它的右边，接着在右边的数组里面差找。

除了这种方法我们还有另外一种方法，数字出现超过一半的意思就是出现的次数加起来超过其他元素出现的总和。

那么我们定义两个变量，一个存储数组中的数字，另外一个就是存储数字出现的次数。

当我们遍历懂啊下一个数字的时候，如果和前一个数字相同，就+1；如果和前一个数字不相同，就-1；

如果次数为0，则保存下一个数字，并将次数设置为1。

这样的话，最后一个把次数设置为1的数字就是我们要找的那个出现次数超过一半的数字。

代码的实现：

#include<iostream>
    using namespace std;
    bool g_bInputInvalid = false;
    bool CheckInvalidArr(int *number, int length)
    {
    	g_bInputInvalid = false;
    	if (number == NULL && length <= 0)
    	{
    		g_bInputInvalid = true;
    	}
    	return g_bInputInvalid;
    }
    bool CheckMoreThanHalf(int* numbers, int length, int number)
    {
    	int times = 0;
    	for (int i = 0; i < length; ++i)
    	{
    		if (numbers[i] == number)
    		{
    			times++;
    		}
    	}
    	bool IsMoreThanHalf = true;
    	if (times * 2 <= length)
    	{
    		g_bInputInvalid = true;
    		IsMoreThanHalf = false;
    	}
    	return IsMoreThanHalf;
    }
    int MoreThanHalfNum(int* numbers, int length)
    {
    	if (CheckInvalidArr(numbers, length))
    	{
    		return 0;
    	}
    	int result = numbers[0];
    	int times = 1;
    	for (int i = 1; i < length; ++i)
    	{
    		if (times == 0)
    		{
    			result = numbers[i];
    			times = 1;
    		}
    		else if (numbers[i] == result)
    		{
    			times++;
    		}
    		else
    		{
    			times--;
    		}
    	}
    	if (!CheckMoreThanHalf(numbers, length, result))
    	{
    		result = 0;
    	}
    	return result;
    }
    int main()
    {
    	int arr[20] = { 0 };
    	cout << "请输入元素的个数->" << endl;
    	int n = 0;
    	cin >> n;
    	cout << "请输入数组的元素->" << endl;
    	for (int i = 0; i < n; i++)
    	{
    		cin >> arr[i];
    	}
    	int ret = MoreThanHalfNum(arr, n);
    	cout << "超过数组一半的数字为：" << ret << endl;
    	system("pause");
    	return 0;
    }

运行的结果：

![Center 1][]![Center 2][]![Center 3][]![Center 4][]

[Center]: /images/20220612/77c33566a38a4d62b701a309e9930357.png
[Center 1]: https://img-blog.csdn.net/20170712191100496?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20170712191105488?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: https://img-blog.csdn.net/20170712191111018?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: /images/20220612/9f91e8fdeb344d5bb718a1ce121d1900.png