百度面试题 --- 锦标赛排序

面了一次百度，暂时完成两轮技术面试，感觉每次都好多题目，并且有一些不知道怎么回答，看来准备的还是不够好。先分享一个题目吧：给出一个长度是N的数组，现在要找出最大的两个元素，最少要多少次比较。分析：如果找出1个最大的，比较次数无疑是 n - 1,现在如果已经找出最大的了，那么再找第二大的，如果用竞赛排序的方法，可以再使用 logn就可以找到了。不过不知道怎么证明这是最小次数。顺便实现了一下竞赛排序。

public class TournamentSort {
private class Node//用node来存储竞赛排序过程中的节点，包括里面的数据和数据在数组中的ID
{
public int data;
public int id;
public Node（）
{
}
public Node（int _data, int _id）//
{
data = _data;
id = _id;
}
}
public void Adjust（Node[] data, int idx）//当去除最小元素以后，我们要调整数组
{
while（idx ！= 0）
{
if（idx % 2 == 1）//当前id是奇数，说明并列的是idx + 1, 父节点是（idx-1）/2
{
if（data[idx].data < data[idx + 1].data）
{
data[（idx - 1）/2] = data[idx];
}
else
{
data[（idx-1）/2] = data[idx + 1];
}
idx = （idx - 1）/2;
}
else
{
if（data[idx-1].data < data[idx].data）
{
data[idx/2 - 1] = data[idx-1];
}
else
{
data[idx/2 - 1] = data[idx];
}
idx = （idx/2 - 1）;
}
}
}
public void Sort（int[] data）
{
int nNodes = 1;
int nTreeSize;
while（nNodes < data.length）
{
nNodes *= 2;
}
nTreeSize = 2 * nNodes - 1;//竞赛树节点的个数, nNode算出来是为了做成满二叉树
Node[] nodes = new Node[nTreeSize];//竞赛树用数组存储
//initialize the data
int i, j;
int idx;
for（ i = nNodes - 1; i < nTreeSize; i++） //初始化竞赛树数据
{
idx = i - （nNodes - 1）;
if（idx < data.length）
{
nodes[i] = new Node（data[idx], i）;
}
else
{
nodes[i] = new Node（Integer.MAX_VALUE, -1）;//对于补充的数据，我们初始化成最大。
}
}
for（ i = nNodes - 2; i >= 0; i--）//
{
nodes[i] = new Node（）;
if（nodes[i * 2 + 1].data < nodes[i * 2 + 2].data）
{
nodes[i] = nodes[i*2 + 1];
}
else
{
nodes[i] = nodes[i*2 + 2];
}
}
//the real sorting procedure
for（ i = 0; i < data.length; i++）//实际排序的过程
{
data[i] = nodes[0].data;//取出最小的
nodes[nodes[0].id].data = Integer.MAX_VALUE;
Adjust（nodes, nodes[0].id）;
}
}
}

百度面试题——需找下一个排列（Find next permuation, POJ 1883）百度面试题---疯子上飞机相关资讯互联网百度百度面试题

30亿网民坐稳啦！互联网之门将要换（今 06:51）
互联网迎来“独立日”？（03月21日）
互联网让我们变聪明了？（11/13/2015 07:53:43）

互联网从开放走向封闭（06月20日）
全球首个互联网网页上线 25 周年（12/21/2015 13:40:02）
古巴的Netflix、Hulu和Spotify不在（09/28/2015 07:00:59）

本文评论查看全部评论（0）