[LeetCode]88.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.


【分析】

【代码】

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 88.Merge Sorted Array
*   来源:https://oj.leetcode.com/problems/merge-sorted-array/
*   结果:AC
*   来源:LeetCode
*   博客:
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        if(n <= 0){
            return;
        }//if
        int indexA = 0,indexB = 0;
        while(indexA < m && indexB < n){
            // B数组元素插入A数组中
            if(A[indexA] >= B[indexB]){
                // 后移一位
                for(int i = m-1;i >= indexA;i--){
                    A[i+1] = A[i];
                }//for
                A[indexA] = B[indexB];
                m++;
                indexB++;
            }//if
            indexA++;
        }//while
        // 如果B数组还没有遍历完
        while(indexB < n){
            A[indexA++] = B[indexB++];
        }//while
    }
};

int main() {
    Solution solution;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int m = 5;
    int n = 6;
    solution.merge(A,m,B,n);
    // 输出
    for(int i = 0;i < 11;i++){
        cout<<A[i]<<" ";
    }
    cout<<endl;
}


【代码二】

The idea is to go from the last indexes of both arrays, compare and put elements from either A or B to the final position, which can easily get since we know that A have enough space to store them all and we know size of A and B. Please refer to the comments for details.

/*********************************
*   日期:2015-01-05
*   作者:SJF0115
*   题目: 88.Merge Sorted Array
*   来源:https://oj.leetcode.com/problems/merge-sorted-array/
*   结果:AC
*   来源:LeetCode
*   博客:
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        if(n <= 0){
            return;
        }//if
        int indexA = m-1,indexB = n-1,cur = m + n -1;
        // AB数组从后往前扫描
        while(indexA >= 0 && indexB >= 0){
            if(A[indexA] < B[indexB]){
                A[cur--] = B[indexB--];
            }//if
            else{
                A[cur--] = A[indexA--];
            }//else
        }//while
        // 如果B数组没有遍历完
        while(indexB >= 0){
            A[cur--] = B[indexB--];
        }//while
    }
};

int main() {
    Solution solution;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int m = 5;
    int n = 6;
    solution.merge(A,m,B,n);
    // 输出
    for(int i = 0;i < 11;i++){
        cout<<A[i]<<" ";
    }
    cout<<endl;
}





目录
相关文章
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
41 0
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
49 0
Search in Rotated Sorted Array - 循环有序数组查找问题
Search in Rotated Sorted Array - 循环有序数组查找问题
72 0
LeetCode 167 Two Sum II - Input array is sorted(输入已排序数组,求其中两个数的和等于给定的数)
给定一个有序数组和一个目标值 找出数组中两个成员,两者之和为目标值,并顺序输出
88 0
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
7月前
|
Python
使用array()函数创建数组
使用array()函数创建数组。
136 3
|
2月前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
2月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
|
2月前
|
存储 JavaScript 前端开发
JavaScript Array(数组) 对象
JavaScript Array(数组) 对象
27 3