遍历查找最大最小值

题目很简单，只要会一些变成功底的，都能写出来，比如以下代码

//简单示例，不追求绝对的可用
//示例1
void Find(std::vector<int> aData, int& minValue,int& maxValue)
{
	if(aData.empty())
		return;
	minValue=aData[0];
	maxValue=aData[0];
	for(size_t i = 0; i<aData.size();++i)
	{
		if(minValue>aData[i])
			minValue=aData[i[;
		if(maxValue<aData[i])
			maxValue=aData[i]
	}
}

嗯，很简单，以上的代码，比较次数复杂度O(2n)，但是如果要求比较次数复杂度降低到O(1.5n)呢，那就要进行优化，看以下代码

//示例2
void Find(std::vector<int> aData, int& minValue,int& maxValue)
{
	if(aData.empty())
		return;
	minValue=aData[0];
	maxValue=aData[0];
	size_t i = 0;
	for(; i+2<aData.size();i+=2)
	{
		if(aData[i] > aData[i+1])
		{
			if(minValue>aData[i+1])
				minValue=aData[i+1[;
			if(maxValue<aData[i])
				maxValue=aData[i]
		}
		else
		{
			if(minValue>aData[i])
				minValue=aData[i[;
			if(maxValue<aData[i+1])
				maxValue=aData[i+1]
		}
	}
	
	//最后可能多一次比较
	if(i<aData.size())
	{
		if(minValue > aData[i+1])
			minValue=aData[i+1];
		if(maxValue<aData[i+1])
			maxValue=aData[i+1];
	}
}

以上比较次数复杂度降低为O(1.5n)

比较次数复杂度 怎么算出来的呢？

示例1，遍历每个元素，都进行2次比较，所以n个元素，就是2n次；
示例2，看着写法更繁琐一些，但每2个元素，进行了3次比较，也就是n个元素要进行1.5n次；

ps，当然，示例2可能会有剩余1个元素，最后还得比较下，可以忽略不算比较次数复杂度；

最后

以上就是单纯皮卡丘为你收集整理的遍历查找最大最小值的全部内容，希望文章能够帮你解决遍历查找最大最小值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。