讨论一个算法，GOOGLE的一个面试题

前五轮，不用我多说了。关键是下来的。
分析：
   如果有可能，总的前五名中,最多会有几个每一轮的第五名。答案很显然是1个。那么第四，第三，第二，第一呢。分别是，一个，一个，两个,五个。
问题的关键出现了。就因为第三名最多只会出现一个，如果把所有的第三名都比一下的话，比的结果是，只取其中的第一名，以外的马都可以排除，这样我们就可以排除12匹马。
如图：(第六轮结果)
1 1 1 1 1
2 2 2 2 2
3 * * * *
4 * * * *
5 * * * *
同理我们如果在第六轮比的是所有的第二名的话，也会排除(12匹)。
1 1 1 1 1
2 2 * * *
3 3 * * *
4 4 * * *
5 5 * * *
（小小的一个发现，就当抛砖引玉。我还没得出最终结论！）

我的答案是:至少7场,最多10场.
我相信这个应该是正确答案,毕竟我看来前面所有人都分析.

但我开始也很疑惑,我看题目就想到了外部排序,准备使用归并排序来做.
把25匹马分成5组,分别排序(比赛),然后把有序的5组两两合并.最后合并为一个有序的组.然后取前5名.搞定问题.

不过当我写出归并排序后,再看题意,感觉不应该这样做,毕竟是最好的方式找到前5名.而不是一个排序的问题.至少不需要知道所有的名次.

改变思路后,发现留言已经到了11页.哈哈...我就不多说了,高兴自己还是想出来了.

随便把归并的代码贴上来吧

package com.jason.stu.algorithm;

import java.util.Arrays;

/**
 * 归并排序
 * 
 * @author Jason
 * 
 */
public class MergeSort {

	public static int[] merge(int[] a, int[] b) {

		int m = 0, n = 0, i = 0;
		int size = a.length + b.length;
		int[] result = new int[size];

		while (m < a.length && n < b.length) {
			result[i++] = (a[m] < b[n]) ? a[m++] : b[n++];
		}

		if (m == a.length)
			for (int t = n; t < b.length; t++)
				result[i++] = b[t];
		else if (n == b.length)
			for (int t = m; t < a.length; t++)
				result[i++] = a[t];

		return result;
	}

	public static void main(String[] args) {
		int[] data1 = { 0, 6, 2, 3, 4 };
		int[] data2 = { 1, 7, 8, 5 };

		Arrays.sort(data1);
		Arrays.sort(data2);

		for (int n : merge(data1, data2))
			System.out.println(n);
	}
}

最少7场，最多9场
末尾比较淘汰
前5场相同，
第六场：各组的number 1比赛，
按第六场的结果有快到慢依次分为
a1,a2,a3,a4,a5
b1,b2,b3,b4,b5
c1,c2,c3,c4,c5
d1,d2,d3,d4,d5
e1,e2,e3,e4,e5
第七场：e1,a2,b2,c2,d2比赛
如果e1第一，则结果出现：a1,b1,c1,d1,e1入围前五
否则，e组被淘汰，此时已经入围的分两种情况
1.a2第一，则入围的最少，只有a1,a2
2.第一为(b2,c2,d2)其中一个，则入围的有3个了a1,([b1,b2],[c1,c2],[d1,d2]),此种情况肯定<=9场了
下面以第一中情况继续比赛
第八场：(针对第七场中a2第一继续)，d1,b2,c2,a3,a4进行比赛
1）d1第一，ok，a1,a2,b1,c1,d1入围
2）d1=2，d组被淘汰,
  其中
  1、a3第一，[a3,b1,c1]入围
  2、c2 or b2 第一，则[b1,c1,c2] or [b1,b2]入围，此时肯定<=9***************情况1
3）d1<2
其中
1、b2orc2第一，则[b1,b2]or[b1,c1,c2]入围，总次数<=9***********************情况2
2、a3第一，[a3]入围，此时剩2个名额了，
    (1)如果a4第二，在a4,a5,b1,b2,c1中取前二**********************************情况3
    (2)a4<2,b2,or c2第二，则[b1,b2] or [b1, c1, c2]入围******************情况4
第九场：执行情况1 or 2 or 3 or 4,此为最坏情况

不好意思，最后情况3是在a4,a5,b1,c1中取前二，b2肯定没用了

1、先赛5场，按照快慢分成五个队列：
1) a1,a2,a3,a4,a5
2) b1,b2,b3,b4,b5
3) c1,c2,c3,c4,c5
4) d1,d2,d3,d4,d5
5) e1,e2,e3,e4,e5
2、第六场：每一对的第一名出来比赛（a1,b1,c1,d1,e1），假设快慢就是给出的这个顺序。
3、第七场：e1与a2,a3,a4,a5进行比赛。
   e1在这两种情况下结果出来：
     1)情况一：e1,a2,a3,a4,a5;(a1,b1,c1,d1,e1)是最快的
    2)情况二：a2,e1,a3,a4,a5; (a1,a2,b1,c1,d1)是最快的但是a2排第几不知道 
*******决出结果。
     3)情况三：a2,a3,e1,a4,a5时，a2,a3需要和b1,c1,d1进行比赛，选出最快的4匹(8场)
     4)情况四：a2,a3,a4,e1,a5时，a2和b1一定在最快的5匹马中，不用参加比赛，a3,a4,c1,d1进行比赛，选出最快的两匹（8场）。（原因是：从[a2,a3,a4]和[b1,c1,d1]这两个排好序的队列中选出最快的四个时，每个序列最多入选3个，那么剩下的一个必然是另外一个队列的第一个元素）
     5)情况五：a2,a3,a4,a5,e1是，此时需要从队列[a2,a3,a4,a5]和[b1,c1,d1]选出最快的4匹马需要进行一场或者两场比赛。
总结：最坏情况是9场，理想情况是5场
                        

其实我觉得这个问题就是外排序，找本数据结构的书就知道了

第一次随机挑5匹马,取最快一匹,然后从剩下的20匹中每次挑一批和其余4匹比,每次都挑出最快一p,21轮后,淘汰4匹,
依次类推,每次淘汰4p,
一共是 21+17+13+9+5=65 次比赛后,剩5匹最快的.

这个应该说对了~

最少10场，情况是前5名是A1,A2,A3,A4,A5
最多16场，情况是A1,B1,C1,D1,E1

我的意见：
5场，选出每组的第一 a1,b1,c1,d1,e1
第6场，选出最快 a1
第7场，我推论是，将b1跟a2,a3,a4,a5比，如果a2,a3,a4,a5其中一个比b1大，
那么第8场可以忽略c,d,e组再拿b1与a中剩下的3个比，如果每次都是a的大，
那么一共10次。

最多的情况区别在第7场，如果b1比a2,a3,a4,a5都大，那么第8场c1就需要跟
a2,a3,a4,a5,b2,b3,b4,b5比，这样需要比2场，如此类推比到e的时候，需要
6+1+2+3+4 = 16
个人意见，纯属消遣