题目原文:Suppose that the subarray a[0] to a[n-1] is sorted and the subarray a[n] to a[2*n-1] is sorted. How can you merge the two subarrays so ...
题目原文:
Suppose that the subarray a[0] to a[n-1] is sorted and the subarray a[n] to a[2*n-1] is sorted. How can you merge the two subarrays so that a[0] to a[2*n-1] is sorted using an auxiliary array of length n (instead of 2n)
分析:
对两个大小分别为n的有序子数组进行归并,要求空间复杂度为n,正常情况下归并排序在此处的空间复杂度为2n,但是由于两个子数组分别是有序的,故用大小为n的额外子空间辅助归并是个很合理的要求,实现如下:
1 import java.util.Arrays; 2 import edu.princeton.cs.algs4.StdRandom; 3 4 public class MergeSortedSubArray { 5 private static boolean less(Comparable v, Comparable w) { 6 return v.compareTo(w) < 0; 7 } 8 public static void merge(Comparable[] array){ 9 int n = array.length/2;10 Comparable[] aux = new Comparable[n];11 for(int i=0;i<n;i++){ //取左半边sorted的元素至辅助数组,因为未来归并左侧位置可能会被右侧元素占据12 aux[i] = array[i];13 }14 System.out.println(Arrays.toString(aux));15 int l = 0;16 int r = n;17 for(int k = 0; k<2*n;k++){18 if(l >= n) break;//辅助元素数组全部用完,array右侧不需要挪动位置了19 else if(r>=2*n) array[k]=aux[l++];//array原右侧元素全部放置合适位置,后面只需把辅助数组的元素挪到array右侧20 else if(less(array[r],aux[l])) array[k] = array[r++];21 else array[k] = aux[l++];22 }23 }24 25 public static void main(String[] args){26 int n = 10;27 int[] subarray1 = new int[n];28 int[] subarray2 = new int[n];29 for (int i = 0; i < n; i++) {30 subarray1[i] = StdRandom.uniform(100);31 subarray2[i] = StdRandom.uniform(100);32 }33 Arrays.sort(subarray1);34 Arrays.sort(subarray2);35 Integer[] array = new Integer[2*n];36 for(int i = 0; i<n;i++){37 array[i] = subarray1[i];38 array[n+i] = subarray2[i];39 }40 System.out.println(Arrays.toString(array));41 merge(array);42 System.out.println(Arrays.toString(array));43 }44 }
海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理:https://www.xlkjsw.com
原标题:Coursera Algorithms week3 归并排序 练习测验1: Merging with smaller auxiliary array
关键词:排序
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。