查找一个数组中超过一半的元素

发布时间:2020-06-20 16:50:36 作者:Sekai_Z
来源:网络 阅读:326

程序1.0

    思想:现将数组排序,再找出元素

void Arraysort(int *a, int length)//冒泡O(n^2)
{

	for (size_t i = 0; i < length; i++)
	{
		for (size_t j = 1; j <length - 1 - i; j++)
		{
			if (a[j]>a[j + 1])
				swap(a[j], a[j + 1]);
		}
	}
}
int MorethanHalfNumber(int *a, int length)
{
	Arraysort(a, length);
	int count = 1;
	for (size_t i = 0; i < length-1; i++)
	{
		if (a[i] == a[i + 1])
		{
			count++;
			if (count == (length + 1) / 2)
				return a[i];
		}
		else
			count = 1;
	}
	return 0;
}

时间复杂度太大,不好

程序1.1 改进

    思想:如果数组中的一个数字出现的次数超过数组长度的一半,如果要排序,那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字

    利用快速排序,先在数组中随机选择一个数字,然后调整数字中数字的顺序,使比选中的数字小数字都排在左边,反之则在右边,如果选中的数字下标为n/2,那么这个数字就是数组的中位数,如果选中的数字下标大于n/2则中位数在左边,接着在它的左边部分的数组中查找。。。利用递归完成

bool CheckMoreThanHalf(int *a, int length, int number)
{
	int count = 0;
	for (int i = 0; i < length; i++)
	{
		if (a[i] == number)
			count++;
	}
	
	if (count * 2 <= length)
		return false;
	return true;
}
int MorethanHalfNumber(int *a, int length)
{
	if ((a == NULL) || length <= 0)
		return 0;
	int mid = length >> 1;
	int start = 0;
	int end = length - 1;
	int index = Partition(a, length, start, end);//快排
	
	while (index != mid)
	{
		if (index > mid)
		{
			end = index - 1;
			index = Partition(a, length, start, end);
		}
		else
		{
			start = index + 1;
			index = Partition(a, length, start, end);
		}
	}
	int result = a[mid];
	if (!CheckMoreThanHalf(a, length, result))
		result = 0;
	return result;
}

程序2.0

    根据数组特点找出O(N)算法

    在遍历数组的时候保存两个值,一个数组的第一个数字,一个是次数,当遍历到下一个数字时,若果下一个数字和我们之前保存的数字相同,则次数加1,如果下一个数字和之前保存的数字不同,次数减1,如果次数为0,我们保存下一个数字,并把次数设为1。由于要找的数字出现的次数一定比其他所有数字出现的次数之和还要多,那么要找的数字肯定是最后一次把次数设为1时的数字

bool CheckMoreThanHalf(int *a, int length, int number)
{
	int count = 0;
	for (int i = 0; i < length; i++)
	{
		if (a[i] == number)
			count++;
	}

	if (count * 2 <= length)
		return false;
	return true;
}
int MorethanHalfNumber(int *a, int length)
{
	if ((a == NULL) || length <= 0)
		return 0;

	int result = a[0];
	int count = 1;
	for (int i = 1; i < length; i++)
	{
		if (count == 0)
		{
			result = a[i];
			count = 1;
		}
		else if (a[i] == result)
			count++;
		else
			count--;
	}
	if (!CheckMoreThanHalf(a, length, result))
		result = 0;
	return result;
}


推荐阅读:
  1. 剑指offer:数组中出现次数超过一半的数字
  2. 数组中出现次数超过数组长度一半的数字

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

offer 剑指 一个数组

上一篇:SSH无密码登录方法及对应的机制

下一篇:java StringBuilder和StringBuffer

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》