零代码自助建站平台,如何做app 的模板下载网站,东莞网站制作搜索祥奔科技,免费网站app下载汅api最近开始刷LintCode上的题目#xff0c;先从标签为容易的开始刷。今天刷的这两题目差不多为同一类型的题目#xff0c;都是为按照一定的规则合并两个已经有序的数组。 [Q6] 描述#xff1a; 合并两个排序的整数数组A和B变成一个新的数组。 样例#xff1a; 给出A[1,2,3,4]先从标签为容易的开始刷。今天刷的这两题目差不多为同一类型的题目都是为按照一定的规则合并两个已经有序的数组。 [Q6] 描述 合并两个排序的整数数组A和B变成一个新的数组。 样例 给出A[1,2,3,4]B[2,4,5,6]返回 [1,2,2,3,4,4,5,6] 思路 题目的方法原型为 1 public int[] mergeSortedArray(int[] A, int[] B) {} 所以即从A和B数组中一次取数比较大小将其中较小者放入新的数组C。 当其中一个数组已经全部取出则将剩余一个数组中的数全部放入数组C中。 在归并排序中当把一个序列分解为若干个子序列之后正是通过递归的合并子序列来完成排序。 实现 1 public int[] mergeSortedArray(int[] A, int[] B) {2 // Write your code here3 4 int[] C new int[A.length B.length];5 6 int indexa 0; //表示a数组的索引位置7 int indexb 0; //表示b数组的索引位置8 int indexc 0; //表示c数组的索引位置9
10 //当某个数组已经全部合并进新的数组的时候跳出循环
11 while( ! ((indexa A.length) || (indexb B.length))){
12 if(A[indexa] B[indexb]){
13 C[indexc ] A[indexa ];
14 }
15 else{
16 C[indexc ] B[indexb ];
17
18 }
19 }
20 //A数组还有剩余元素
21 while(indexa A.length){
22 C[indexc ] A[indexa ];
23 }
24 //B数组还有剩余元素
25 while(indexb B.length){
26 C[indexc ] B[indexb ];
27 }
28
29 return C;
30
31 } [Q64] 描述 合并两个排序的整数数组A和B变成一个新的数组。 你可以假设A具有足够的空间A数组的大小大于或等于mn去添加B中的元素。 样例 给出 A [1, 2, 3, empty, empty], B [4, 5] 合并之后 A 将变成 [1,2,3,4,5] 思路 题目的方法原型为 1 public void mergeSortedArray(int[] A, int m, int[] B, int n) {} 从题目函数原型和题目描述可以看出这次在合并的时候是在A数组的基础上进行合并A数组的大小大于或等于AB的大小所以可以将B数组合并到A数组中。 考虑两种情况 1 当B中的某个元素已经比A中的最后一个元素还要大时此时不需要再继续比较了直接将B中包括当前元素的剩余元素全部插入到A数组最后。 2 当B中的第x元素通过比较插入到了A数组的y位置上则第x 1 元素直接从y 1 位置开始继续比较前面的无需比较。 此题目比上面的题目还要多增加一个步骤因为是在A数组上进行插入所以插入之后插入位置以后的元素需要往后移动一个位置涉及到一个移动操作。 实现 1 public void mergeSortedArray(int[] A, int m, int[] B, int n) {2 int indexa 0 ; // 标识A数组的遍历位置3 int indexb 0 ; //标识B数组的遍历位置4 int lastIndex m - 1 ; //标识A数组中最后的位置5 6 while ( (indexa lastIndex) (indexb n - 1) ) {7 if(B[indexb] A[indexa]){8 //这个题目第一此提交出现了错误 错误原因是下面的for循环中应该是i -- , 手滑写成了 i 9 for(int i lastIndex ; i indexa ; i --){
10 A[i 1] A [i] ;
11 }
12 A[indexa ] B[indexb ];
13 lastIndex ;
14 }
15 else{
16 indexa ;
17 }
18 }
19 while(indexb n - 1 ) {
20 A[ lastIndex] B[indexb ] ;
21 }
22 } 总结 有关于数组的操作大多可以用过设置不同变量来标识数组中的不同位置从而可以进行不同的操作。 转载于:https://www.cnblogs.com/tancky/p/6574747.html
