阿里笔试小结

舞会上有n-1个群众和1个明星，所有的群众都认识明星，群众之间相互是否认识并不确定，明星不认识任何一个群众，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度

遍历1~n这n个人；
首先取出1号和2号，如果1认识2，那么把1去掉；如果1不认识2，就可以把2去掉了。
如果2认识1，那么把2去掉；
如果1和2都互相不认识，把他们都去掉； 
如果有剩下，再拿剩下的和3号进行比较；
如果没有剩下的，则拿出3号和4号进行比较；

如此循环；
最后若剩下最后1个人，再遍历一遍看是否剩下的n-1个人都认识它

时间复杂度分析：
每对之间的比较最多比较2次， 每对之间的比较至少淘汰1个人，要淘汰n-1个人最多比较 2*（n-1）次；
所以时间复杂度是 O（n）

有一个淘宝卖家，他在全国有n个仓库，这n个仓库正好构成一个环形，即1->2->3->4......->n-1->n->1的环，开始他所有仓库的货物数是不定的，现在他想让所有仓库的货物数都相等，如何运输这些货物使得运输量最少，运输只能在两个相邻的仓库之间发生。试设计算法。

我们令a[i]为第i个仓库的初始货物数,ave为每个仓库的目标货物数
假设a[1]与a[n]的货物交换数为k(k为正表示a[1]提供给a[n],为负表示a[n]提供为a[1]),则可以得到如下信息:
    
a[1]的运输次数:|a[1]-k-ave|(如果a[1]减去k后比ave大/小,则需要与a[2]交换|a[1]-k-ave|)
此时a[2]的货物数为a[2]+a[1]-k-ave,则a[2]的运输次数为:|a[2]+a[1]-k-ave-ave|,整理得|a[1]+a[2]-k-2*ave|

同理可得:

a[3]的运输次数为:|a[1]+a[2]+a[3]-k-3*ave|
...
a[n-1]的运输次数为:|a[1]+a[2]+...+a[n-1]+k-(n-1)*ave|

而a[n]的运输次数则为|k|,当然你也可以理解成a[1]的运输次数为|K|+|a[1]-k-ave|,a[n]运输次数为0

我们令sum[i]表示从a[1]加到a[i]减掉i*ave的和,则总共的运输次数为:
|sum[1]-k|+|sum[2]-k|+...+|sum[n-1]-k|+|k|

显然当k为sum数组的中位数是,总运输次数最小

有n（n>4）个士兵，他们每个人都掌握属于自己的情报，如果两个士兵之间交换一次情报，就能拥有对方的情报，现在设计一种交换次数最少的算法，使得所有士兵都能拥有全部情报，并给出最少的交换次数。

4个士兵需要4次：
1－2，3－4，1－3，2－4
6个士兵需要8次，
1－2，3－4，5－6，1－3，1－5，3－6，2－1，4-1