java高级算法问题求解 牛人请进

Question

1）N个已经排序好的数组，每个数组有M个数字，给出一个算法把这N个数组合并成一个排好序的大数组，并分析该算法的时间和空间复杂度。

2）写一个Java函数最高效的实现字符串倒序（不能直接使用类库API）。

3）用Java数组实现一个先进先出的Queue。

Answer 1

1 可以参考我的一篇博文
http://robblog.iteye.com/admin/blogs/566114
使用堆排序进行多路数组合并。

2
[code="java"] public static char[] reverseStr(final char[] oriStr) {
char[] ret = new char[oriStr.length];
for (int i = 0; i < oriStr.length; i++)
ret[i] = oriStr[oriStr.length - i - 1];
return ret;
}

public static void main(String[] args) {
    char[] oriStr = { 'b', 'c', 'd', 'a', 'f' };
    System.out.println(reverseStr(oriStr));
}[/code]

3 说下思路
使用一个数组保存进入队列的值，分别用两个变量保存队头和队尾，需要考虑：

• 入队： 在队尾插入元素，队尾加1
• 出队： 返回队头，队头加1
• 空队列： 队头索引和队尾索引相同
• 数组扩张和缩小： 由于数组定义时必须指定长度，可以先指定一个长度，当队列中的元素个数将要大于这个长度是，扩张数组，队列长度过小时缩小数组。如果扩张数组： 可以参考ArrayList中的实现。