【题目】
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 tom+n) to hold additional elements from B. The number of elements initialized in A and B aremandnrespectively.
【分析】
无
【代码】
/*********************************
* 日期: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;
}
分享到:
相关推荐
Merge Sorted Array 合并 排序 数组 leetcode
Merge Sorted Array vi. Sum vii. Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range ...
lru缓存leetcode leetcode ...Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
26 | [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp) [Python](./Python/remove-duplicates...
88.Merge Sorted Array(c++) 00 94.Binary Tree Inorder Traversal(c++:tree traversal inorder) 100.Same Tree(c++) 101.对称树(c++) 104.二叉树的最大深度(c++) 108.将排序数组转换为二叉搜索树
leetcode添加元素使和等于 LeetCodeNotes Array: 4. Median of Two Sorted Arrays 思路: 基于二分查找的思想 88. Merge Sorted Array 描述:合并两个有序数组,将B合并入A,A长度刚好为A.length + B.length nums1 =...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
Leetcode经典01背包 algo 1. 数据结构与算法 数组,链表,(串和序列) 堆,栈,队列 树,图 排序,搜索 贪心,回溯,动态规划 堆:一种完全二叉树,任意节点大于左右孩子(大顶堆) 树:二叉树,DFS,BFS 1 排序与...
20 Merge Sorted Array 61 ... ... 231 Counting Bits 561 232 Maximum Product of Word Lengths 563 233 Gray Code 565 234 Permutations 567 235 Permutations II 571 236 Permutation Sequence 573 237 Generate ...
88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of Binary Tree) 118.杨辉三角 (Pascal's Triangle) 119.杨辉三角 II (Pascal's Triangle)
leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum ...Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ
leetcode 跳跃 leetcode 按题型标签,记录...合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-conversion.md) [0030 串联所有单词的子串](./String/substring
liwangStudy note for leetcode.Easy001 Two SumUsing hash map.020 Valid ParenthesesUsing stack can achieve O(n) space and O(n) time.Using Regular match, the complexity depends on the regular algorithm....
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。...Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
总览 ... 例如, merge-sorted-array.py的解决方案位于https://leetcode.com/problems/merge-sorted-array/ 。 Leetcode类似问题 我发现一起解决类似的问题很有意义,这样当我们遇到新问题时,我们可以
Merge Two Sorted Lists] [53. Maximum Subarray] [70. Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is ...
Merge Two Sorted Lists Easy #26 Remove Duplicates from Sorted Array Easy #27 Remove Element Easy #35 Search Insert Position Easy #38 Count and Say Easy #53 Maximum Subarray Easy #66 Plus One Easy #70 ...
Leetcode Python解决方案和解释。 也是准备软件工程师面试的指南。 概述这是我的Python(2.7)Leetcode解决方案。 随着时间的流逝,这也成为准备...例如,merge-sorted-array.py的解决方案位于https://leetcode.com/pr
例如,merge-sorted-array.py 的解决方案位于 https://leetcode.com/problems/merge-sorted-array/。 Leetcode 类似问题我发现将类似问题一起解决是有意义的,这样我们在遇到新问题时可以更快地识别问题。 我的...
Leetcode算法练习 Leetcode算法练习 ...MaximumSubarray 58_LengthOfLastWord 66_PlusOne 67_AddBinary 69_Sqrt(x) 70_ClimbStairs 83_RemoveDuplicatesFromSortedList 88_MergeSortedArray 100_SameT