O(n)复杂度，求数组中第2大的数

为什么我反对纯算法面试

提及一条算法题目，查找一个数组中第二大的数。

 

第二大数，直接想到的是，先遍历一次数组，把最大的取出来。然后再遍历一次，把最大的取出来。总耗费时间复杂度O(n + n -1)

还有没有其他O(n)的算法呢？

 

先挖坑，在填坑，都到凌晨2点了，明天想下

 

早上起来，想了下，跟上次连续子数组的思维差不多，用两个数字保存最大的两个数值，大的放前面，第二大的放后面，然后在遍历过程中穷举各种情况即可。

public class kmax{
	public static void main(String[] args){
		int[] a = new int[]{1,3,-2,32,-3,5};
		System.out.println(get2ndMax(a));
	}
	public static int get2ndMax(int[] a){
		//max[0]存放最大值，max[1]存放第二最大值
		int[] max = new int[2];
		if(a[0]>a[1]){
			max[0] = a[0];
			max[1] = a[1];
		}else{
			max[0] = a[1];
			max[1] = a[0];
		}

		for(int i=2;i<a.length;i++){
			//穷举，其实就2种情况
			if(a[i]>max[0]){
				max[1] = max[0];
				max[0] = a[i];
			}else if(a[i]>max[1]){
				max[1] = a[i];
			}
		}
		return max[1];
	}
}

 

---

 去中大打完球回来，除了一身汗，把想到的位图方法也写上吧。编程珠玑中使用位图排序实现了O(n)的排 序，让我大开眼界，原来在特定条件下，O(n)排序也是可能的。既然O(N)的排序都有了，查找第2大的数字也没问题。假定数组的数字都是整数，上限是 MAX，下限是MIN。算法的复杂度是O（2*(MAX-MIN))。

 

public class BitmapKmax{
	public static void main(String[] args){
		int[] a = new int[]{-20,-29,32,99,29,10,39,42,28};
		System.out.println(get2ndMax(a,-100,100));
	}
	
	public static int get2ndMax(int[] a, final int MIN, final int MAX){
		if(a.length<2){
			throw new IllegalArgumentException("array must contain at least 2 elements");
		}
		int secondMax = 0;
		byte[] byteArr = new byte[(MAX-MIN)/8 + 1];
		for (int i=0; i<a.length; i++) {
			int v = a[i]-MIN;
			int index = v/8;
			int v2 = v%8;
			byteArr[index] = (byte)(byteArr[index] | (1<<v2));
		}
		for (int i=0, count=0; i<byteArr.length; i++) {
			if(byteArr[i]!=0){
				for(int j=0;j<8;j++){
					if(0 != (byteArr[i] & (1<<j))){
						count++;
					}
					if(2 == count){
						secondMax = i*8 + j;
						break;
					}
				}
				if(2 == count){
					break;
				}
			}
		}
		return secondMax+MIN;
	}
	
}

 

至于他文章中所说的那个同学没有用O(n)的方法去做，而是用排序，我也挺佩服的。说实话，我也忘了O(nlogn)的快排怎么写了，呵呵，只记得用了分治递归的思想。嗯，下次我也尝试不看书的情况写个快排。

 

各位看官，不知道有没有其他方法，请不吝笔墨，大书特书。

 

 

评论

8 楼 libofeng 2013-04-16  

第一个解法简单明了

7 楼 ansjsun 2013-04-16  

lazy_ 写道

ansjsun 写道

大概看了下代码...
这么排啊...其实答案应该是堆排...

第二大是 O(2*logn)  = O(n)

不对呀。你构建一个堆也花了O(N*logN)。期待你的回复，最好有代码。

全排序是O(N*logN).

如果只找出第n大 就是 O(n*logN) ;

代码网上好多的...你得看看堆的性质..每次弹出一个最大的...

6 楼 lazy_ 2013-04-16  

ansjsun 写道

大概看了下代码...
这么排啊...其实答案应该是堆排...

第二大是 O(2*logn)  = O(n)

不对呀。你构建一个堆也花了O(N*logN)。期待你的回复，最好有代码。

5 楼 chinaagan 2013-04-15  

ansjsun 写道

大概看了下代码...
这么排啊...其实答案应该是堆排...

第二大是 O(2*logn)  = O(n)

不错

4 楼 ansjsun 2013-04-15  

大概看了下代码...
这么排啊...其实答案应该是堆排...

第二大是 O(2*logn)  = O(n)

3 楼 kidneyball 2013-04-15  

robin_liang 写道

O(n + n -1)和O(n)有区别吗？

在算法复杂度上没区别，在转化为实际程序后执行效率上有区别。算法复杂度只是一个用来衡量算法运算量跟输入数据规模的比例关系的工具（例如是无关，或是线性关系，或是指数关系），不等同于算法所对应程序的实际执行效率。算法复杂度相同的算法在写成实际程序后执行效率是可能有区别的。

前几天还在微博上跟前某创新院的某名博扯这个问题……他用一段O(n)的预处理弄出来一个链表，然后做了一个O(n)的顺序搜索。我用一段O（n)的预处理弄出来一个数组，然后做了一个O(logn)的二分搜索。他楞是要说我们的两种处理的时间是一致的（原话是我的做法在时间上没有优化），因为O(n+n) = O(n + logn) = O(n)。我问他：那是不是做了一次O（n）的预处理后，后面再跟一万个O(n)，和把这一万个O(n)都改成O(logn)时间是一样的？ 他答：本来就是这样……

2 楼 backkom1982 2013-04-15  

求第N大的数，都可以在O(n)复杂度能完成。

先分成每组包含N个的多个小组，N是大于等于5的奇数，然后再会分而治之的方法寻找第N大的数。

具体思路可见：
http://www.shrekwang.com/article/52001/%E5%AF%BB%E6%89%BE%E7%AC%ACk%E5%A4%A7%E7%9A%84%E6%95%B0%E7%9A%84O(n)%E7%AE%97%E6%B3%95

1 楼 robin_liang 2013-04-15  

O(n + n -1)和O(n)有区别吗？