归并算法之有序数组合并算法实现
归并算法之有序数组合并算法实现
一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组。实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部。再将另一个数组剩下的所有元素,直接放入归并数组尾部。算法的简单实现,需要注意的是对参数的校验,判断数组是否有序。
public class MergeOrderedArray { public static int[] merge(int [] a,int []b){ if(!isOrderedArray(a)){ System.out.println(" array a is not an ordered array."); return null; } if(!isOrderedArray(b)){ System.out.println(" array b is not an ordered array."); return null; } int a_len = a.length; int b_len = b.length; int[] merge = new int[a_len+b_len]; int i=0,j=0,k=0; while(i<a_len&&j<b_len){ if(a[i]<b[j]){ merge[k++]=a[i++]; }else{ merge[k++]=b[j++]; } } //A数组全部合并完毕,将b数组剩余直接加入合并数组 if(i==a_len){ for(;j<b_len;j++){ merge[k++]= b[j]; } }else{ for(;i<a_len;i++){ merge[k++]= a[i]; } } return merge; } public static boolean isOrderedArray(int [] array){ if(array==null||array.length==0){ return false; } for(int i = 0;i<array.length-1;i++){ if(array[i]>array[i+1]){ return false; } } return true; } public static void main(String[] args) { int a [] = {1,2,3,4,5}; int b [] = {2,3,4,5,6,7,8,9}; int [] merge = merge(a,b); System.out.println(Arrays.toString(merge)); } }
算法的时间复杂度,取决于待合并的两个数组的长度,所以是O(M+N),空间复杂度也是O(M+N),即需要的归并数组的长度是M+N。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关推荐
-
用递归查找有序二维数组的方法详解
假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中.假设一个4×4的有序二维数组: 1 2 8 9 2 4 9 12 4 7 10 13 6 8
-
java实现向有序数组中插入一个元素实例
整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha
-
合并有序数组的实现(java与C语言)
合并有序数组的实现 java版本: 实例代码 public class Merge { //合并有序数组 public static void mergeSort(int a[], int b[], int c[]) { int n = a.length, m = b.length; int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) { c[k++] = a[i++]; } else
-
javascript 折半查找字符在数组中的位置(有序列表)
复制代码 代码如下: /** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var lowPoint=1; var higPoint=array.length; var returnValue=-1; var midPoint; var found=false; whi
-
C语言实现在数组A上有序合并数组B的方法
本文实例讲述了C语言实现在数组A上有序合并数组B的方法,分享给大家供大家参考.具体分析如下: 题目:数组A和数组B均有序,数组A有足够大内存来容纳数组B,将数组B有序合并到数组A中 分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include <iostream> #include <algorithm> #include <iterator>
-
php实现有序数组打印或排序的方法【附Python、C及Go语言实现代码】
本文实例讲述了php实现有序数组打印或排序的方法.分享给大家供大家参考,具体如下: 有序的数组打印或排序对于php来讲非常的简单了这里整理了几个不同语言的做法的实现代码,具体的我们一起来看这篇php中有序的数组打印或排序的例子吧. 最近有个面试题挺火的--把2个有序的数组打印或排序,刚看到这个题的时候也有点蒙,最优的算法肯定要用到有序的特性. 思考了一会发现也不是很难,假如数组是正序排列的,可以同时遍历2个数组,将小的值进行排序,最后会遍历完一个数组,留下一个非空数组,而且剩下的值肯定大于等于已
-
js有序数组的连接问题
1.前言 昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题.但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件. 2.简单但效率不高的算法 我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下: 复制代码 代码如下: function concatSort(arrA,arrB){ return arrA.concat(arrB).sort(); } 为了弄清楚sort排序到
-
php判断一个数组是否为有序的方法
本文实例讲述了php判断一个数组是否为有序的方法.分享给大家供大家参考.具体分析如下: 这段代码的时间复杂度为O(n) <?php function JudegSortArray($array) { if ($array [0] > $array [1]) { $flag = 1; } else { $flag = 0; } $temp = $flag; $len = count ( $array ); for($i = 1; $i < $len; $i ++) { if ($flag
-
Python实现二维有序数组查找的方法
本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角
-
归并算法之有序数组合并算法实现
归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组.实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部.再将另一个数组剩下的所有元素,直接放入归并数组尾部.算法的简单实现,需要注意的是对参数的校验,判断数组是否有序. public class MergeOrderedArray { public static int[
-
java实现把两个有序数组合并到一个数组的实例
如下所示: package com.test.sort; public class testMerge { public static void main(String[] args) { int[] a = { 1, 3, 5 }; int[] b = { 2, 3, 4, 7 }; merge m = new merge(); m.method(a, b); } } class merge { public void method(int[] a, int[] b) { int l = a.
-
iOS常用算法之两个有序数组合并(要求时间复杂度为0(n))
思路: 常规思路: 先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去; 简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去. 代码如下: - (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 { // 全为空不处理 if (!array1.
-
详解Java数据结构和算法(有序数组和二分查找)
一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默
-
KnockoutJS数组比较算法实例详解
这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击
-
C++实现两个有序数组的合并
本文实例为大家分享了C++实现两个有序数组合并的具体代码,供大家参考,具体内容如下 剑指offer面试题5延展题: 问题:有两个排序的数组A1和A2,内存在A1的末尾有足够多的空间容纳A2.请实现一个函数,把A2中所有数字插入A1中,并且所有的数字是排序(默认升序)的. 思路:在合并两个数组(包括字符串)时,从前往后复制每个数字(或字符)则需要重复移动数字(或字符)多次,则考虑从后往前复制就可以减少移动的次数,从而提高效率. 1.n1,n2分别指向数组A1和A2的尾部,strNew指向合并后的数
-
Python实现的合并两个有序数组算法示例
本文实例讲述了Python实现的合并两个有序数组算法.分享给大家供大家参考,具体如下: 思路 按位循环比较两个数组,较小元素的放入新数组,下标加一(注意,较大元素对应的下标不加一),直到某一个下标超过数组长度时退出循环 假设两个源数组的长度不一样,那么假设其中短的数组用完了,即全部放入到新数组中去了,那么长数组中剩下的那一段就可以直接拿来放入到新数组中去了. #coding=utf-8 #合并数据 test1 = [1,2,5,7,9] test2=[2,4,6,8,10,11,34,55] d
-
JS实现的合并多个数组去重算法示例
本文实例讲述了JS实现的合并多个数组去重算法.分享给大家供大家参考,具体如下: var arr1 = ['a','b']; var arr2 = ['a','c','d']; var arr3 = [1,'d',undefined,true,null]; //合并两个数组,去重 var concat_ = function(arr1,arr2){ //不要直接使用var arr = arr1,这样arr只是arr1的一个引用,两者的修改会互相影响 var arr = arr1.concat();
-
java算法入门之有效的括号删除有序数组中的重复项实现strStr
目录 1.LeetCode 20.有效的括号 题目 小编菜解 思路及算法 大神解法 2.LeetCode 26.删除有序数组中的重复项 题目 小编菜解初版 小编菜解改进版 思路及算法 大神解法 3.LeetCode 28.实现strStr 题目 小编菜解 大神解法 也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1
-
PHP实现合并两个有序数组的方法分析
本文实例讲述了PHP实现合并两个有序数组的方法.分享给大家供大家参考,具体如下: $arr1 = array(1,2,3,4,5,6,7,8); $arr2 = array(3,4,5,7,9,10); //方法1 function mergeOrderly1($arr1,$arr2){ $i=0;$j=0; $int = array(); while($i<count($arr1) && $j<count($arr2)){ $int[] = $arr1[$i]<$arr
随机推荐
- 如何用拦截表单的方法上传图片?
- css别忘记清除浮动clear:both
- JavaScript 解析Json字符串的性能比较分析代码
- PHP针对常规模板引擎中与CSS/JSON冲突的解决方法
- 浅谈iOS 数据结构之链表
- perl用{}修饰变量名的写法分享
- C#操作txt文件,进行清空添加操作的小例子
- Python itertools模块详解
- C#实现rabbitmq 延迟队列功能实例代码
- PHP数组及条件,循环语句学习
- Ajax方式删除表格一行数据示例代码
- 基于Lucene的Java搜索服务器Elasticsearch安装使用教程
- Linux管理员手册(7)--管理用户帐户
- php 5.6版本中编写一个PHP扩展的简单示例
- Nginx 的多站点配置方案
- 深度理解c++中的this指针
- 在ASP.NET 2.0中操作数据之四:使用ObjectDataSource展现数据
- Python 创建空的list,以及append用法讲解
- Python多线程同步---文件读写控制方法
- iOS中UITextField实现过滤选中状态拼音的代码