澳门正规赌博十大网站-澳门游戏网站
做最好的网站

澳门赌场排名app:练习测验1,快速排序

澳门赌场排名app:练习测验1,快速排序。Coursera Algorithms week3 归并排序 练习测验1: Merging with smaller auxiliary array,courseraweek3

题目原文:

Suppose that the subarray a[0] to a[n-1] is sorted and the subarray a[n] to a[2*澳门赌场排名app:练习测验1,快速排序。n-1] is sorted. How can you merge the two subarrays so that a[澳门赌场排名app:练习测验1,快速排序。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 }

 

Algorithms week3 归并排序 练习测验1: Merging with smaller auxiliary array,courseraweek3 题目原文: Suppose that the subarray a[0] to a[n-1] is sorted and th...

Coursera Algorithms week3 快速排序 练习测验: Selection in two sorted arrays(从两个有序数组中寻找第K大元素),courseraalgorithms

题目原文

Selection in two sorted arrays. Given two sorted arrays a[] and b[], of sizes n1 and n2, respectively, design an algorithm to find the kth largest key. The order  of growth of the worst case running time of your algorithm should be logn, where n = n1 n2.

Version 1 : n1 = n2 and k = n/2

Version 2: k = n/2

Version 3: no restrictions

分析:

 这个题目是要求从两个有序数组中寻找第K大元素,直观解法就是把连个数组归并排序,这样时间复杂度就是O(n),但是题目只要求知道第K大元素,其余比K大的元素的排列顺序并不关心。

默认数组a和数组b都是从小到大排序的。不论第K大元素在a或b中,其右侧元素一定大于K,可考虑分别从a和b中排除右侧(k-1)/2个元素,剩下的就是在未排除区间寻找第(k-已排除元素)大元素。通过递归逐步缩小比较范围。具体算法见如下代码。

 1 package week3;
 2 
 3 import java.util.Arrays;
 4 import edu.princeton.cs.algs4.StdRandom;
 5 
 6 public class KthInTwoSortedArrays {
 7     /**
 8      * 寻找第K大元素
 9      * @param a 数组a
10      * @param alo a的查找区间下界
11      * @param ahi a的查找区间上界
12      * @param b 数组b
13      * @param blo b的查找区间下界
14      * @param bhi b的查找区间上界
15      * @param k 当前查找区间的第k大元素
16      * @return
17      */
18     private static int find(int[] a, int alo, int ahi,int[] b, int blo, int bhi, int k){
19         if(alo > ahi) return b[bhi-k 1];
20         if(blo > bhi) return a[ahi-k 1];
21         if(k==1) return a[ahi] > b[bhi]? a[ahi]:b[bhi];
22         //直接用bhi-(k-1)/2或ahi-(k-1)/2进行查找可能会将第K个元素给漏掉
23         int bt = bhi-(k-1)/2 > blo ? bhi-(k-1)/2:blo;
24         int at = ahi-(k-1)/2 > alo ? ahi-(k-1)/2:alo;
25         if(a[at] >= b[bt]) 
26             return find(a,alo,at-1,b,blo,bhi,k-(ahi-at 1));
27         else
28             return find(a,alo,ahi,b,blo,bt-1,k-(bhi-bt 1));
29     }
30     
31     public static void main(String[] args){
32         int n = 10;
33         int n1 = StdRandom.uniform(n);
34         int n2 = n-n1;
35         int[] a = new int[n1];
36         int[] b = new int[n2];
37         for(int i=0;i<n1;i  ){
38             a[i] = StdRandom.uniform(100);
39         }
40         for(int i=0;i<n2;i  ){
41             b[i] = StdRandom.uniform(100);
42         }
43         Arrays.sort(a);
44         Arrays.sort(b);
45         System.out.println("a=" Arrays.toString(a));
46         System.out.println("b=" Arrays.toString(b));
47         int[] c = new int[n];
48         int i = 0;
49         int j = 0;
50         int l = 0;
51         while(l<n){
52             if(i>=n1) c[l  ] = b[j  ];
53             else if(j>=n2) c[l  ] = a[i  ];
54             else{
55                 if(a[i] <= b[j])
56                     c[l  ] = a[i  ];
57                 else
58                     c[l  ] = b[j  ];
59             }
60                 
61         }
62         System.out.println("c=" Arrays.toString(c));
63         
64         int k =StdRandom.uniform(1,n);
65         int largestK = find(a,0,n1-1,b,0,n2-1,k);
66         System.out.println("第" k "大元素是:" largestK);
67     }
68 }

 

Algorithms week3 快速排序 练习测验: Selection in two sorted arrays(从两个有序数组中寻找第K大元素),courseraalgorithms 题目原文 Selection in...

本文由澳门正规赌博十大网站发布于澳门游戏网站,转载请注明出处:澳门赌场排名app:练习测验1,快速排序