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

本文实例讲述了C语言实现在数组A上有序合并数组B的方法，分享给大家供大家参考。具体分析如下：

题目：数组A和数组B均有序，数组A有足够大内存来容纳数组B，将数组B有序合并到数组A中

分析：如果由前至后合并，复杂度将会是O(N2)，这样的复杂度显然不是最优解，利用两个指针指向两个数组的尾部，从后往前遍历，这样的复杂度为O(n2)

由此可以写出下面的代码：

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int arrayA[10] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};
const int sizeB = sizeof arrayB / sizeof *arrayB;
const int sizeA = sizeof arrayA / sizeof *arrayA - sizeB;

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = sizeB - 1;

 while (posA >= 0 && posB >= 0)
 {
 if (arrayA[posA] < arrayB[posB])
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 else
 {
  arrayA[posA + posB + 1] = arrayA[posA];
  posA--;
 }
 copy(arrayA, arrayA + 10, ostream_iterator<int>(cout, " "));
 system("pause");
 }

 return arrayA;
}

void main()
{
 int *result = mergeArray(arrayA, sizeA, arrayB, sizeB);

 copy(result, result + 10, ostream_iterator<int>(cout, " "));
 cout << endl;
}

代码写完后似乎完成了所需功能，但还不止于此，必须对上述代码做UT

1. 健壮性

arrayA或arrayB为空，长度小于0

2. 边界用例

arrayA为空，长度为1；arrayB不为空，长度大于1
首元素用例
const int size = 6;
int arrayA[size] = {2};
int arrayB[] = {0, 1, 1, 1, 1};
反之
const int size = 6;
int arrayA[size] = {0, 1, 1, 1, 1};
int arrayB[] = {2};

3. 正常用例：

const int size = 10;
int arrayA[size] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};

const int size = 10;
int arrayA[size] = {2, 4, 6, 8, 10};
int arrayB[] = {1, 3, 5, 7, 9};

const int size = 10;
int arrayA[size] = {1, 2, 3, 4, 5};
int arrayB[] = {6, 7, 8, 9, 10};

const int size = 10;
int arrayA[size] = {6, 7, 8, 9, 10};
int arrayB[] = {1, 2, 3, 4, 5};

经过上面的测试，不难发现在边界条件用例中，代码已经不能正确运行出结果，在测试用例的驱动下，不难写出正确代码如下：

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = sizeB - 1;

 while (posA >= 0 && posB >= 0)
 {
 if (arrayA[posA] < arrayB[posB])
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 else
 {
  arrayA[posA + posB + 1] = arrayA[posA];
  posA--;
 }
 copy(arrayA, arrayA + size, ostream_iterator<int>(cout, " "));
 system("pause");
 }

 //出现两种情形：
 //1. posA < 0 && posB >= 0
 //2. posA >= 0 && posB < 0
 //只有第1种情形需要进行处理
 if (posA < 0 && posB >= 0)
 {
 while (posB >= 0)
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 }
 return arrayA;
}

相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。

赞 (0)

相关推荐

  • 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

  • js有序数组的连接问题

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

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

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

  • 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

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

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

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

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

    假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中.假设一个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

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

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

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

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

  • 深入理解C语言中使用频率较高的指针与数组

    深入理解C语言中使用频率较高的指针与数组

    目录 定义 指针与二维数组 指针数组与数组指针 数组指针的应用 操作 总结 定义 指针:C语言中某种数据类型的数据存储的内存地址,例如:指向各种整型的指针或者指向某个结构体的指针. 数组:若干个相同C语言数据类型的元素在连续内存中储存的一种形态. 数组在编译时就已经被确定下来,而指针直到运行时才能被真正的确定到底指向何方.所以数组的这些身份(内存)一旦确定下来就不能轻易的改变了,它们(内存)会伴随数组一生. 而指针则有很多的选择,在其一生他可以选择不同的生活方式,比如一个字符指针可以指向单个字符

  • C语言的数组学习入门之对数组初始化的操作

    数组在所有的语言中,以C最为简单,就是一起始地址,外加一数组的长度,而且基本上没有任何功能可言.然而,在所有的数组使用中,却是C的这种简单的数组形式,以其灵活性和效率,让人惊叹. C数组从逻辑上讲,是分形一致的(想不到其他词来形容了),分形的意思,就是部分与整体保持一致的构造形式,也即是数组的任何一部分也都是数组,比如一整型数组{1,2,3,4,5},连续取出其中任一连续的部分,都可以看成是一个数组,{2,3}是数组,{1,2,3}是数组,{4,5}也都是数组,差别只在于数组的起始地址和元素的个

  • C语言从txt文件中逐行读入数据存到数组中的实现方法

    首先,要知道数据的存储格式是怎样的, 65 2 722 542 691 514 644 506 588 524 565 558 608 580 648 586 696 572 482 564 第一行表示数字的个数和维数,所以要先读入这些信息: <span style="white-space:pre"> </span>FILE *fp = fopen("2D_Jesscia_keypos.txt", "r"); if (

  • 详解C语言用malloc函数申请二维动态数组的实例

    详解C语言用malloc函数申请二维动态数组的实例 C语言在程序运行中动态的申请及释放内存十分方便,一维数组的申请及释放比较简单. Sample one #include <stdio.h> int main() { char * p=(char *)malloc(sizeof(char)*5);//申请包含5个字符型的数组 free(p); return 0; } 是否申请二维动态内存也如此简单呢?答案是否定的.申请二维数组有一下几种方法 Sample two /* 申请一个5行3列的字符型

  • 易语言合并数组的方法

    易语言是一款全中文编程软件,其中数组的使用困扰了很多人,今天教大家将数组合并! 1.打开易语言,新建一个Windows窗口程序 2.在窗口中加入三个按钮,命名为数组1,数组2,合并数组 3.接下来是按钮的代码 .版本 2 .支持库 spec .程序集 窗口程序集_启动窗口 .程序集变量 数组1, 文本型, , "0" .程序集变量 数组2, 文本型, , "0" .子程序 _按钮1_被单击 数组1 ＝ { "0", "1",

  • R语言-在一张图上显示多条线的实现

    R语言-在一张图上显示多条线的实现

    查询百度之后,发现在R上一次显示多张图的函数很多,比如layout()或者分屏函数,但是这些都不是我想要的结果. 之后,发现了line()函数可以保留原来图片继续作图,在括号中填入所需画图的部分即可(我是将一个矩阵作图). 先运行plot()函数,再注释掉plot()函数运行line()函数即可. 效果如下: 补充:R语言:在同一张图作不同曲线 R语言将两条曲线作在同一张图的方法是 library(ggplot2) year<-c(1993,1998,2003,2008) Res<-c(0.0

  • R语言入门在CentOS服务器上配置RStudio Server

    R语言入门在CentOS服务器上配置RStudio Server

    目录 安装R 安装并部署RStudio Server 过程中遇到的问题 这里主要参考如下网址进行R与RStudio Server的配置与部署. Download RStudio Server 在部署完成后,可在官方说明文件中查看详细的使用方法: RStudio Server Professional Edition 安装R 我们的环境是CentOS7-中文,并且是root账户. 然后我们按照前面参考网址中的说明,找到对应的系统,首先安装EPEL(注意,必须先安装EPEL后面才能成功安装R): s

  • Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

    目录 题目描述 思路分析 AC 代码 题目描述 961. 在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums ,该数组具有以下属性: nums.length == 2 * n. nums 包含 n + 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素. 示例 1: 输入:nums = [1,2,3,3] 输出:3 示例 2: 输入:nums = [2,1,2,5,3,2] 输出:2 示例 3: 输入:nums = [5,1,5,

随机推荐