java高级算法问题 牛人请进

襄阳城

<p>java高级算法问题 牛人请进</p>
<p><img src="http://img.baidu.com/img/iknow/icn_point.gif"> 悬赏分：100 -</p>
<p>解决时间：2010-2-25 12:55</p>
<p>1）N个已经排序好的数组，每个数组有M个数字，给出一个算法把这N个数组合并成一个排好序的大数组，并分析该算法的时间和空间复杂度。</p>
<p>2）写一个Java函数最高效的实现字符串倒序（不能直接使用类库API）。</p>
<p>3）用Java数组实现一个先进先出的Queue。</p>
<p>求解答</p>
<p>提问者： 80705041 - 六级</p>
<p>最佳答案</p>
<p>第一个，其实类似于 Merge Sort 中的合并一步：</p>
<p>思路是每个小数组进行 select，然后插入大数组：</p>
<p>假设顺序是从小到大：</p>
<p>----------------------------- CODE --------------------------------</p>
<p>import java.util.Random;</p>
<p>public class Sort {</p>
<p>public static void main (String args[]) {</p>
<p>Random rnd = new Random();</p>
<p>final int N=5， M=8;</p>
<p>// Generate random array:</p>
<p>int[][] src = new int[N][M];</p>
<p>for (int i=0; i<N; i++)</p>
<p>src[0] = rnd.nextInt(50);</p>
<p>for (int i=0; i<N; i++) {</p>
<p>for (int j=1; j<M; j++)</p>
<p>src[j] = src[j-1] + rnd.nextInt(20);</p>
<p>}</p>
<p>// Print out the src arrays:</p>
<p>for (int i=0; i<N; i++) {</p>
<p>for (int j=0; j<M; j++)</p>
<p>System.out.print(src[j] + " ");</p>
<p>System.out.println();</p>
<p>}</p>
<p>// Sort:</p>
<p>int[] sorted = new int[M*N];</p>
<p>int[] length = new int[N];        //record the length of each array</p>
<p>for (int i=0; i<N; i++)</p>
<p>length = M;</p>
<p>int min = 0;</p>
<p>int j = 0;</p>
<p>for (int i=0; i<sorted.length; i++) {</p>
<p>for (j=0; j<N; j++)</p>
<p>if (length[j] != 0)</p>
<p>break;</p>
<p>if (j==5)</p>
<p>break;</p>
<p>min = j;</p>
<p>for (j=0; j<N; j++) {</p>
<p>if (length[j] == 0)</p>
<p>continue;</p>
<p>if (src[j][0] < src[min][0])</p>
<p>min = j;</p>
<p>}</p>
<p>sorted = src[min][0];</p>
<p>for (j=1; j<length[min]; j++)</p>
<p>src[min][j-1] = src[min][j];</p>
<p>length[min] --;</p>
<p>}</p>
<p>// Print out the result:</p>
<p>System.out.println();</p>
<p>for (int i=0; i<sorted.length; i++)</p>
<p>System.out.print(sorted + " ");</p>
<p>}</p>
<p>}</p>
<p>---------------------------- END CODE -----------------------------</p>
<p>时间复杂度：O(n平方)</p>
<p>空间复杂度：O(n)</p>
<p>****************************************</p>
<p>第二题，这个以前做过，很简单，代码如下：</p>
<p>----------------------------- CODE --------------------------------</p>
<p>public class Reverse {</p>
<p>public static String reverse (String arg0) {</p>
<p>char[] reverse_c = new char[arg0.length()];</p>
<p>for (int i=0; i<reverse_c.length; i++)</p>
<p>reverse_c = arg0.charAt(reverse_c.length-i-1);</p>
<p>return (new String(reverse_c));</p>
<p>}</p>
<p>public static void main (String args[]) {</p>
<p>if (args.length > 0)</p>
<p>System.out.println(reverse(args[0]));</p>
<p>}</p>
<p>}</p>
<p>---------------------------- END CODE -----------------------------</p>
<p>运行：java Reverse "Hello， world!!"</p>
<p>!!dlrow ，olleH</p>
<p>****************************************</p>
<p>第三题：</p>
<p>----------------------------- CODE --------------------------------</p>
<p>public class Queue<E extends Comparable> {</p>
<p>private E[] queue;</p>
<p>@SuppressWarnings("unchecked")</p>
<p>public Queue (int capacity) {</p>
<p>queue = (E[])new Object[capacity];</p>
<p>}</p>
<p>public Queue () {</p>
<p>this(10);</p>
<p>}</p>
<p>public void offer (E element) {</p>
<p>for (int i=queue.length-1; i>0; i--)</p>
<p>queue = queue[i-1];</p>
<p>queue[0] = element;</p>
<p>}</p>
<p>public E peek () {</p>
<p>return queue[queue.length-1];</p>
<p>}</p>
<p>public E poll () {</p>
<p>E head = queue[queue.length-1];</p>
<p>queue[queue.length-1] = null;</p>
<p>return head;</p>
<p>}</p>
<p>public int getCapacity () {</p>
<p>return queue.length;</p>
<p>}</p>
<p>}</p>
<p>---------------------------- END CODE -----------------------------</p>
<p>没有写测试类，但估计是没问题的。可以自己试一下。</p>
<p>0</p>
<p>回答者：</p>
<p><img src="http://img.baidu.com/img/iknow/icon_lights.gif"></p>
<p>shuangwhywhy - 九级   2010-2-24 11:32</p>
<p>我来评论>></p>
<p>提问者对于答案的评价：</p>
<p>leyang2008 在javaeye已经帮我解决了，还是谢谢你给出的思路，哈哈，多谢了</p>