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

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

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

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

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中的实现。