C++实现两个有序数组的合并

2024-04-21 10:57:54

本文实例为大家分享了C++实现两个有序数组合并的具体代码，供大家参考，具体内容如下

剑指offer面试题5延展题：

问题：有两个排序的数组A1和A2，内存在A1的末尾有足够多的空间容纳A2。请实现一个函数，把A2中所有数字插入A1中，并且所有的数字是排序（默认升序）的。

思路：在合并两个数组（包括字符串）时，从前往后复制每个数字（或字符）则需要重复移动数字（或字符）多次，则考虑从后往前复制就可以减少移动的次数，从而提高效率。

1.n1,n2分别指向数组A1和A2的尾部，strNew指向合并后的数组的尾部；
2.当数组名是一个nullptr指针，或者A1数组是一个空数组则返回；
3.当数组A1[ida]>=A2[idb]或者idb<0时，则复制ida指针所指的数到strNew指向的位置，ida向前移动1格，strNew向前移动1格；
4.当数组A1[ida]<A2[idb]或者ida<0时，则复制idb指针所指的数到strNew指向的位置，idb向前移动1格，strNew向前移动1格；
5.直到strNew<0则停止循环。

注意：

输入的n1,n2为数组的长度，作指针时都要-1；
循环终止的条件从合并数组指针入手，合并结束循环终止，即strNew<0；
注意形参和实参的传递，数组传入函数的三种声明func(int *arr), func(int arr[n]), func(int arr[])，返回数组指针的函数int * func( )

#include<iostream>
#include<stdio.h>
using namespace std;

int * insert(int *str1, int *str2, int n1, int n2,int length){
  //int *dest = str1;
  if(str1 == nullptr || str2 == nullptr || length <= 0){
    return 0;
  }
  int strNew = n1 + n2 - 1;
  int ida = n1-1;
  int idb = n2-1;
  while(strNew >= 0){
    if(str1[ida] >= str2[idb] || idb<0){
      str1[strNew--] = str1[ida];
      ida--;
    }
    else if(str1[ida] < str2[idb] || ida<0){
      str1[strNew--] = str2[idb];
      idb--;
    }
  }
  return str1;
  //return dest;
}

int main()
{
  int n1,n2;
  cin>>n1>>n2;
 int a[n1],b[n2];
  for(int i = 0; i<n1; ++i){
    cin>>a[i];
  }
  for(int i=0;i<n2;++i){
    cin>>b[i];
  }
  //int *c;
  //c = insert(a, b, n1, n2, 100);
  insert(a, b, n1, n2, 100);
  for(int i=0;i<n1+n2;++i){
    cout<<a[i]<<' ';
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++实现合并两个排序的链表

本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下问题描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN
浅谈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
C++实现两个有序数组的合并

本文实例为大家分享了C++实现两个有序数组合并的具体代码,供大家参考,具体内容如下剑指offer面试题5延展题: 问题:有两个排序的数组A1和A2,内存在A1的末尾有足够多的空间容纳A2.请实现一个函数,把A2中所有数字插入A1中,并且所有的数字是排序(默认升序)的. 思路:在合并两个数组(包括字符串)时,从前往后复制每个数字(或字符)则需要重复移动数字(或字符)多次,则考虑从后往前复制就可以减少移动的次数,从而提高效率. 1.n1,n2分别指向数组A1和A2的尾部,strNew指向合并后的数
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
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.
Python实现的合并两个有序数组算法示例

本文实例讲述了Python实现的合并两个有序数组算法.分享给大家供大家参考,具体如下: 思路按位循环比较两个数组,较小元素的放入新数组,下标加一(注意,较大元素对应的下标不加一),直到某一个下标超过数组长度时退出循环假设两个源数组的长度不一样,那么假设其中短的数组用完了,即全部放入到新数组中去了,那么长数组中剩下的那一段就可以直接拿来放入到新数组中去了. #coding=utf-8 #合并数据 test1 = [1,2,5,7,9] test2=[2,4,6,8,10,11,34,55] d
go语言题解LeetCode88合并两个有序数组示例

目录题目描述思路分析 AC 代码题目描述原题链接 : 88. 合并两个有序数组给你两个按非递减顺序排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目. 请你合并 nums2 到 nums1 中,使合并后的数组同样按非递减顺序排列. 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素
Python3合并两个有序数组代码实例

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

今天在于硬件进行交互的过程中,要到了了需要两个数组进行合并,然后对数组进行反转和加密操作,以下是两个byte数组合并的方法. /** * * @param data1 * @param data2 * @return data1 与 data2拼接的结果 */ public static byte[] addBytes(byte[] data1, byte[] data2) { byte[] data3 = new byte[data1.length + data2.length]; Syste
Python寻找两个有序数组的中位数实例详解

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

C++实现两个有序数组的合并

相关推荐

随机推荐