数据结构面试题总结1——数组：求最大、次大值

一般大家一开始想到的办法就是一次循环，记录下最大值和最小值。或者就是用两次冒泡，找到最大值和次大值。

这两种方法实践复杂度差不多都是O(2n)，如果数组很长，效率还是不够高的。

注意：直接排序，再选择最大的两个值，这并不是一个好办法，因为我们只需要前两个数有序，不需要后N-2个数有序。

冒泡方法我就不帮大家实现了。编程的细节要注意，数组a只是个示例，如果有负值，max和second_max的初始化要最小，以免出错。

int main(int argc, char* argv[])
{
	int a[] = {1,2,3,4,5,6,7,8,9};
	int max = 0;
	int second_max = 0;
	for (int i = 0; i < 9; i++)
	{
		if (a[i] > max)
		{
			second_max = max;
			max = a[i];
		}
		else if (a[i] > second_max)
		{
			second_max = a[i];
		}
	}
	cout << max << endl;
	cout << second_max << endl;
	
	return 0;
}

我们继续思考，最大值和次大值其实就是要两个排序结果，在排序中我们当然有更快的算法（线性排序算法，归并，快速，堆排序），我们有没有办法使用这些方法呢？

想弄清楚上面的问题，我们再看一个此问题的延伸问题，也是很典型的题，编程之美上有的！

查找最大无序量元素中最大的K个数。

这篇文章分析的很棒：http://blog.csdn.net/xiaoding133/article/details/8037086。

看完以后发现第一种方法，就是我们前面所想到的。

第二种方法，依赖快速排序所选择的值，平均复杂度为O(N*logK)，在K为2的时候，平均复杂度O(n)看起来不错，但是效率很不稳定。

第三种方法，用一个k容量的堆，K为2的时候，容量2，高度也为2。乍一看好像不错，但其实和我上面所写的代码是一样的效果。但是这里要注意了，我们可以考虑一下堆排序中的初始堆(大顶堆)建立，建立完后数组的前三位一定包含最大值和次大值，时间复杂度为O(n)。这里用O(n)来比较不太确切，大家可以看看大顶堆建立时间复杂度的推导。

注意：这个方法也只能针对于求前二大值，这是二叉树的特有的。再多就要用此文章中的方法。

第四种方法不好。

第五种方法，就是线性排序的方法，稳定在O(n)，当然这里还需要一点时间去取出最终结果。但是受到容量的限制就没办法用了，还有变量类型，整型。