这是一道数组操作的题目,思路比较明确,就是维护三个index,分别对应数组A,数组B,和结果数组。然后A和B同时从后往前扫,每次迭代中A和B指向的元素大的便加入结果数组中,然后index-1,另一个不动。代码如下:
public void merge(int A[], int m, int B[], int n) {
if(A==null || B==null)
return;
int idx1 = m-1;
int idx2 = n-1;
int len = m+n-1;
while(idx1>=0 && idx2>=0)
{
if(A[idx1]>B[idx2])
{
A[len--] = A[idx1--];
}
else
{
A[len--] = B[idx2--];
}
}
while(idx2>=0)
{
A[len--] = B[idx2--];
}
}
这里从后往前扫是因为这个题目中结果仍然放在A中,如果从前扫会有覆盖掉未检查的元素的可能性。算法的时间复杂度是O(m+n),m和n分别是两个数组的长度,空间复杂度是O(1)。这个题类似的有Merge
Two Sorted Lists,只是后者是对于LinkedList操作,面试中可能会一起问到。
分享到:
相关推荐
Merge Sorted Array 合并 排序 数组 leetcode
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补数据结构和算法的短板 概述 之前写过一个 leetcode 的一点题解,不过后来就断了,现在重新...merge-sorted-array 杨辉三角 pascals-triangle 杨辉三角 II pa
总览 ... 例如, merge-sorted-array.py的解决方案位于https://leetcode.com/problems/merge-sorted-array/ 。 Leetcode类似问题 我发现一起解决类似的问题很有意义,这样当我们遇到新问题时,我们可以
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode 跳跃 leetcode 按题型标签,记录...合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-conversion.md) [0030 串联所有单词的子串](./String/substring
LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于佛系,刷刷题吧...
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
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...
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
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) 69.x 的平方根 (Sqrt(x)) 70.爬楼梯 ...
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 ...
merge 2 sorted array into a 3rd empty array. ##2019-03-28 斐波那契数列(Fibonacci sequence), 又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci) 以兔子繁殖为例子而引入,故又称为...
例如,merge-sorted-array.py 的解决方案位于 https://leetcode.com/problems/merge-sorted-array/。 Leetcode 类似问题我发现将类似问题一起解决是有意义的,这样我们在遇到新问题时可以更快地识别问题。 我的...
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
Leetcode算法练习 Leetcode算法练习 ...MaximumSubarray 58_LengthOfLastWord 66_PlusOne 67_AddBinary 69_Sqrt(x) 70_ClimbStairs 83_RemoveDuplicatesFromSortedList 88_MergeSortedArray 100_SameT
leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum ...Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ
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 ...
leetcode 2 和 ...Array(c++) 00 94.Binary Tree Inorder Traversal(c++:tree traversal inorder) 100.Same Tree(c++) 101.对称树(c++) 104.二叉树的最大深度(c++) 108.将排序数组转换为二叉搜索树
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 ...
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....