iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）

思路:

常规思路:

先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去;

　　简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去.

代码如下:

- (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 {
  // 全为空不处理
  if (!array1.count && !array2.count) {
    return @[];
  }
  // 一个为空返回另外一个
  if (!array1.count) {
    return array2;
  }
  if (!array2.count) {
    return array1;
  }
  NSMutableArray *endArray = [NSMutableArray array];
  while (1) {
    if ([array1[0] integerValue] < [array2[0] integerValue]) {
      [endArray addObject:array1[0]];
      [array1 removeObjectAtIndex:0];
    }else {
      [endArray addObject:array2[0]];
      [array2 removeObjectAtIndex:0];
    }
    if (!array1.count) {
      [endArray addObjectsFromArray:array2];
      break;
    }
    if (!array2.count) {
      [endArray addObjectsFromArray:array1];
      break;
    }
  }
  return endArray;
}

执行代码, 输入输出结果如下:

总结

以上所述是小编给大家介绍的iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）,希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

赞 (0)

相关推荐

  • IOS面试大全之常见算法

    这篇文字给大家分享了IOS面试中熟悉常见的算法,下面来一起看看吧. 1. 对以下一组数据进行降序排序(冒泡排序)."24,17,85,13,9,54,76,45,5,63" int main(int argc, char *argv[]) { int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63}; int num = sizeof(array)/sizeof(int); for(int i = 0; i < num-1; i

  • ios使用OC写算法之递归实现八皇后

    八皇后算法介绍 知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色,她可以上下左右通吃,和中国象棋里面的车(ju 一声)一样,但是她比车更强大,她可以在斜线上也做到通吃,而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后 八皇后算法思路解析 既然任意一个皇后都无法吃掉其他的皇后,也就是说任两个皇后都不能处于同一条横行.纵行或斜线上,我们将棋盘当做一个二维数组,将皇后的位置标记为1 而其他位置默认都为0,这样我们就可以使用

  • iOS中MD5加密算法的介绍和使用

    前言 软件开发过程中,对数据进行加密是保证数据安全的重要手段,常见的加密有Base64加密和MD5加密.Base64加密是可逆的,MD5加密目前来说一般是不可逆的. MD5生成的是固定的128bit,即128个0和1的二进制位,而在实际应用开发中,通常是以16进制输出的,所以正好就是32位的16进制,说白了也就是32个16进制的数字. MD5主要特点是 不可逆,相同数据的MD5值肯定一样,不同数据的MD5值不一样(也不是绝对的,但基本是不能一样的). MD5算法还具有以下性质: 1.压缩性:任意

  • iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）

    思路: 常规思路: 先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去; 简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去. 代码如下: - (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 { // 全为空不处理 if (!array1.

  • 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.

  • 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

  • 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

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

    归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组.实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部.再将另一个数组剩下的所有元素,直接放入归并数组尾部.算法的简单实现,需要注意的是对参数的校验,判断数组是否有序. public class MergeOrderedArray { public static int[

  • 浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    一直到大四才开始写自己的第一篇博客,说来实在有点羞愧.今天写了关于排序的算法题,有插入排序,冒泡排序,选择排序,以下贴上用JAVA实现的代码: public class test5 { public static void print(int []array) //输出数组方法 { for(int i=0;i<array.length;i++) System.out.print(" "+array[i]); } public static void selectsort(int

  • Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数 审题: 1.找出意味着这是一个查找算法题 2.算法复杂度log级别,就是提示你是二分查找 3.二分查找实现一般为递归 (1)递归包括递归体  (2)终止条件 思路: 定理: 1.有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2) 2.如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中比中位数大的k个数,得到的合并子数组的中位数和原来的中位数相同. eg:[1,2

  • Python3合并两个有序数组代码实例

    第一种思路,把两个数组合为一个数组然后再排序,问题又回归到冒泡和快排了,没有用到两个数组的有序性.(不好) 第二种思路,循环比较两个有序数组头位元素的大小,并把头元素放到新数组中,从老数组中删掉,直到其中一个数组长度为0.然后再把不为空的老数组中剩下的部分加到新数组的结尾.(好) 第二种思路的排序算法与测试代码如下: def merge_sort(a, b): ret = [] while len(a)>0 and len(b)>0: if a[0] <= b[0]: ret.appen

  • C++实现LeetCode(两个有序数组的中位数)

    [LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and 

随机推荐