归并算法之有序数组合并算法实现

归并算法之有序数组合并算法实现

一个简单的有序数组合并算法：写一个函数，传入 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。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • 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

  • 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

  • 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

  • js有序数组的连接问题

    1.前言 昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题.但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件. 2.简单但效率不高的算法 我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下: 复制代码 代码如下: function concatSort(arrA,arrB){      return arrA.concat(arrB).sort(); } 为了弄清楚sort排序到

  • php实现有序数组打印或排序的方法【附Python、C及Go语言实现代码】

    本文实例讲述了php实现有序数组打印或排序的方法.分享给大家供大家参考,具体如下: 有序的数组打印或排序对于php来讲非常的简单了这里整理了几个不同语言的做法的实现代码,具体的我们一起来看这篇php中有序的数组打印或排序的例子吧. 最近有个面试题挺火的--把2个有序的数组打印或排序,刚看到这个题的时候也有点蒙,最优的算法肯定要用到有序的特性. 思考了一会发现也不是很难,假如数组是正序排列的,可以同时遍历2个数组,将小的值进行排序,最后会遍历完一个数组,留下一个非空数组,而且剩下的值肯定大于等于已

  • Python实现二维有序数组查找的方法

    本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角

  • 用递归查找有序二维数组的方法详解

    假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中.假设一个4×4的有序二维数组:          1          2          8          9          2          4          9          12          4          7          10        13          6          8 

  • C语言实现在数组A上有序合并数组B的方法

    本文实例讲述了C语言实现在数组A上有序合并数组B的方法,分享给大家供大家参考.具体分析如下: 题目:数组A和数组B均有序,数组A有足够大内存来容纳数组B,将数组B有序合并到数组A中 分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include <iostream> #include <algorithm> #include <iterator>

  • 合并有序数组的实现（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

  • 归并算法之有序数组合并算法实现

    归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 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实现的合并多个数组去重算法示例

    本文实例讲述了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

    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

随机推荐