精华内容
下载资源
问答
  • 两个有序数组的合并

    2019-03-29 16:16:52
    编写一个程序,将两个有序数组合并成一个更大的有序数组,要求时间复杂度为O(n)。 输入 多组数据输入,每组输入包括两行,每行第一个数字为数组长度n,然后输入n个有序整数。 输出 输出合并数组(升序),每...

    数组合并

    题目描述

    编写一个程序,将两个有序数组合并成一个更大的有序数组,要求时间复杂度为O(n)。

    输入

    多组数据输入,每组输入包括两行,每行第一个数字为数组长度n,然后输入n个有序整数。

    输出

    输出合并后的数组(升序),每组输出用一个空行隔开。

    样例输入 Copy

    3 1 3 5
    3 2 4 6
    2 1 2
    4 3 4 5 6
    

    样例输出 Copy

    1 2 3 4 5 6
    
    1 2 3 4 5 6

    其实这就是二分查找的升级版,两个数组都是有序的,我们可以以其中任何一个数组为插入数据的对象,然后遍历另一个数组,如果比当前范围(left-right)的最小的要小,则数组往后移,将这个数放入目前范围内最小的位置;

    若比当前范围内最大的数要大,则将这个数组目前最大范围的最大数后面的数往后移,再将这个数放到目前范围最大的位置;

    上述两种情况都是数字不在范围内,如果数字在范围内,即x>a[left]&&x<a[mid] 或者x>a[mid]&&x<a[right],则不断缩小范围,直到出现上述两种情况;

    用一个全局变量来保存当前已经放了几个数,因为每放一次,数组的长度就会变化,

     

    代码如下:

     

    #include<stdio.h>
    int count=0;//记录数组的变化长度 
    void move(int *a,int n,int k){
        int i=n-1;
        for(;i>=k;i--){
            
            a[i+1]=a[i];
        }
    }

    int binary_search(int *a,int n,int x){
        int left=0,right=n-1;
        int mid;
        while(left<=right){
            mid=(left+right)/2;
            if(x<=a[left]){//比当前区间最小的小 
                move(a,n,left);//数组后移
                a[left]=x; 
                count++;
                return left;
            }
            if(x>=a[right]){//比当前区间最大的大 
                move(a,n,right);
                a[right+1]=x;
                count++;
                return right+1;
            }
            if(x>a[left]&&x<a[mid]){//在区间范围内 
                right=mid-1;
            }else if(x>a[mid]&&x<a[right]){
                left=mid+1;
            }
            
        }
        return -1;
    }
    int main(){
        int n,q;
        while(scanf("%d",&n)!=EOF){    
        int s[1000],t[5000],index;
        count=0;    
        for(int i=0;i<n;i++)
             scanf("%d",&s[i]);
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d",&t[i]);
            index=binary_search(s,n+count,t[i]);
            //printf("%d\n",index);
        }
        for(int i=0;i<n+count;i++){
            printf("%d%c",s[i],i==n+count-1?'\n':' ');
        }
            printf("\n");
        }
        
        return 0;
    }

     

    第一次写博客,多多关照呀呀!!!

    展开全文
  • 主要为大家详细介绍了C++实现两个有序数组的合并,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 看到其他部门的笔试题,发现有这个题目:两个有序数组的合并,于是尝试着用python写出来具体如下:if__name__==‘__main__‘:a=[2,4,6,8,9,10]b=[0,1,3,6,7,9,100,134]counta=countb=0#分别记录两个数组遍历到哪个...

    看到其他部门的笔试题,发现有这个题目:两个有序数组的合并,于是尝试着用python写出来

    具体如下:if __name__ == ‘__main__‘:

    a=[2,4,6,8,9,10]

    b=[0,1,3,6,7,9,100,134]

    counta=countb=0#分别记录两个数组遍历到哪个位置了

    c=[]

    for i in range(counta,len(a)):

    for j in range(countb,len(b)):

    print "b[j]:",j,b[j]

    if(b[j]<=a[i]):

    c.append(b[j])

    countb=countb+1#append了b[j],那么b数组的遍历的记录应该自增

    else:

    c.append(a[i])

    counta=counta+1#append了a[i],那么a数组的遍历的记录应该自增

    break#为啥要break?因为到此位置,说明b数组不能继续往下遍历了,该遍历a了

    #现在就需要吧两个数组中剩余的元素依次append到c中即可

    if (counta

    for i in range(counta,len(a)):

    c.append(a[i])

    if (countb

    for j in range(countb,len(b)):

    c.append(b[j])

    print c

    本文出自 “H2O's运维&开发路” 博客,转载请与作者联系!

    展开全文
  • 算法:两个有序数组的合并

    千次阅读 2014-04-22 22:13:10
    两个有序数组的合并

    LeetCode OJ Problem:Merge Sorted Array

    Given two sorted integer arrays A and B, merge B into A as one sorted array.

    Note:
    You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

    class Solution {
    public:
        void merge(int A[], int m, int B[], int n) {
            if(m == 0)
            {
                while(n)
                {
                    A[n-1] = B[n-1];
                    n--;
                }
                return;
            }
            else if(n == 0)
                return;
            int index = m+n-1;
            while(m && n)
            {
                if(A[m-1] >= B[n-1])
                {
                    A[index] = A[m-1];
                    m--;
                }
                else
                {
                    A[index] = B[n-1];
                    n--;
                }
                index--;
            }
            if(m == 0)
            {
                while(n)
                {
                    A[index] = B[n-1];
                    n--;
                    index--;
                }
            }
        }
    };


    展开全文
  • java两个有序数组的合并 题目来源leetCode 链接:https://leetcode-cn.com/problems/sorted-merge-lcci 题目: 给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A ...

    java两个有序数组的合并

    题目来源leetCode 链接:https://leetcode-cn.com/problems/sorted-merge-lcci
    题目:
    给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A 并排序。
    初始化 A 和 B 的元素数量分别为 m 和 n。
    A.length= n+m;

    public class Test01 {
            public static void main(String[] args) {
                int[] A = {0};
                int m = 0;
                int[] B = {1};
                int n = 1;
                Test01.merge(A, m, B, n);
            }
    //解法一:三指针法
     public static void merge(int[] A, int m, int[] B, int n) {
            //  保存当前两个数组最后元素位置索引
            int indexA=m-1,indexB=n-1;
            //  条件是有一个数组判断完了
            while(indexA>=0 && indexB>=0){
                //  获取A数组最后填充元素的位置
                int index = indexA+indexB+1;
                A[index] = A[indexA]>B[indexB]?A[indexA--]:B[indexB--];
            }
            // 防止A数组先判断完,B数组可能没完全并入A数组
            while(indexB>indexA){
                A[indexB] = B[indexB--];
            }
        }
    }
    
    展开全文
  • java:两个有序数组的合并

    千次阅读 2019-02-27 15:57:05
    两个有序数组的合并 /** * 将两个有序数组合并为一个有序数组 * @param arr1 * @param arr2 * @return */ public static int[] arrayMerge(int[] arr1, int[] arr2){ int len1 = arr1.length; i...
  • 问题描述 编写函数,将两个有序 vector 数组合并成一个新的有序 vector数组,函数原型为: vector<int> merg(vector<...两个有序数组的自身排列方式是升序还是降序; 因此 在函数内先默认两个数组都...
  • 主要介绍了JAVA实现选择排序,插入排序,冒泡排序,以及两个有序数组的合并,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 两个有序数组的合并 public class Main { public static int[] mergeTwoArray(int[] arr1, int[] arr2) { int i = 0; int j = 0; int k = 0; int len1 = arr1.length; int len2 = arr2.length; int[] res = ...
  • 题目:有两个有序数组a和b,将它们合并成数组c,需要c也是有序数组。 具体思路: 将新建一个长度为a和b长度之和数组,将较长数组复制到新数组,将较短数组每个元素插入到指定位置(用到插入排序算法)。 ...
  • java实现两个有序数组的合并

    千次阅读 2016-03-23 10:37:14
    思想:先依次比较两个数组,按照小的就传入新的数组。当这次比较完之后可能有一个数组的长度很长,留下一些... 3 //两个有序数组的合并函数  4 public static int[] MergeList(int a[],int b[])  5 {  6
  • // 两个有序数组的合并排序 function twoArrSort(arr1, arr2) { let i = 0, j = 0 let newArr = [] // arr1 = [5, 3, 1] arr2 = [6, 4, 2] // 第一轮: ewArr = [6] , arr1 = [5, 3, 1], arr2 = [4, 2] //
  • 两个有序数组的合并算法

    千次阅读 2014-02-07 17:26:52
     两个有序数组的合并算法 void addArray(int *ch,int *addch,int len1,int len2) { int *addcur=addch+len2-1; int *cur=ch+len1-1; int *targetch=ch+len1+len2-1; while(targetch>=ch) {
  • 给定两个从小到大排好序的整型数组,要求编写一个函数实现两个有序数组的合并,并保持从小到大的顺序。 如: $arr_A=[1,3,6,9] $arr_B=[2,4,5,8,20] Combine($arr_A,$arr_B) 返回数组 [1,2,3,4,5,6,8,9,20] ...
  • 看到其他部门的笔试题,发现有这个题目:两个有序数组的合并,于是尝试着用python写出来关键:1、两个数组已经排序好,所以内部无需比较,比较都是存在于两个数组之间2、比较结束后,需要将其中一个数组的剩余序列...
  • 看到其他部门的笔试题,发现有这个题目:两个有序数组的合并,于是尝试着用python写出来关键:1、两个数组已经排序好,所以内部无需比较,比较都是存在于两个数组之间2、比较结束后,需要将其中一个数组的剩余序列...
  • 题目:有两个有序数组a,b,现需要将其合并成一个新有序数组。简单思路就是先放到一个新数组中,再排序。但是这样没体现任何算法,这里考不是快速排序等排序算法。关键应该是如何利用 有序 已知这个条件。...
  • 思路:在合并两个数组(包括字符串)时,从前往后复制每个数字(或字符)则需要重复移动数字(或字符)多次,则考虑从后往前复制就可以减少移动次数,从而提高效率。 n1,n2分别指向数组A1和A2尾部,strNew指向...
  • 1.两个有序单链表的合并 typedef struct ListNode{ int val; ListNode* next; }ListNode; ListNode* mergeList(ListNode* pHead1,ListNode* pHead2){ if (pHead1==NULL) return pHead2; if (pHead2 == NULL) ...
  • 问:如何实现两个有序数组的合并(以int类型数组为例),合并成一个有序数组面试官如果抛出这个问题,答案会有很多种,比如插入排序,比如快速排序,还有归并排序,当然首先应该想到的就是归并排序如果面试官问我这...
  • 给定两个有序数组a[m],b[n],要求将这两个数组合并陈一个数组,时间复杂度最大为O(n),辅助空间为O(1) 分析: 设sum控制合并数组,a1控制合并前a数组,b1控制合并前b数组,sum,a1,b1都是从最后一位开始(这...
  • public static void main(String[] args) { int[] a=new int[]{1,6,9,122}; int[] b=new int[]{2,3,4}; int[] temp=new int[7]; int[]d= compareDG(a,0,b,0,temp,0); fo...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,929
精华内容 1,971
关键字:

两个有序数组的合并