Merge Sorted Array
来自 <https://leetcode.com/problems/merge-sorted-array/>
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.
题目解读:
给定两个整型数组nums1 和nums2,将数组nums2中的元素归并到数组nums1中。题目已经假设数组nums1 中拥有足够的空降将数组nums2 中的元素加入到其中。
解析:
方法一:按照最常规的方法从前往后归并。申请一个空间为m+n的数组nums3 ,将两个数组中的元素归并到数组nums3 中,程序结束时再将数组nums3 中的元素复制到数组nums1 中。此方法必须申请额外的空间来存储数组nums3 ,并且在还得数组nums3 中的数据复制到数组nums1 中,此方法拥有较高的时间和空间复杂度。
方法二:
从后向前归并。由于数组nums1 拥有足够的空间可以容纳m+n个元素,则可以利用nums1中的空间进行从后向前归并。i记录nums1中最后一个元素的位置,j记录nums2中最后一个元素的位置,k记录两个数组归并后最后一个元素的位置。图解如下图所示
Java 代码
public void merge(int[] nums1, int m, int[] nums2, int n) { if((nums1==null) && (nums2==null)) return; /** * 记录nums1中最后一个元素的位置 */ int i = m-1; /** * 记录nums2中最后一个元素的位置 */ int j = n-1; /** * 记录归并结束后最后一个元素的位置 */ int k = m+n-1; while ((i>=0) && (j>=0)) { if(nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } //add remains elements to result while(j>=0) { nums1[k--] = nums2[j--]; } for(int a: nums1) System.out.print(a + ","); }
算法性能
相关推荐
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补数据结构和算法的短板 概述 之前写过一个 leetcode 的一点题解,不过后来就断了,现在重新...merge-sorted-array 杨辉三角 pascals-triangle 杨辉三角 II pa
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 ...
88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of Binary Tree) 118.杨辉三角 (Pascal's Triangle) 119.杨辉三角 II (Pascal's Triangle)
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
总览 ... 例如, 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
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....
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
462 | [Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/) | [C++](./C++/minimum-moves-to-equal-array-elements-ii.cpp) [Python](./Python/...
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 2 sorted array into a 3rd empty array. ##2019-03-28 斐波那契数列(Fibonacci sequence), 又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci) 以兔子繁殖为例子而引入,故又称为...
leetcode 跳跃 leetcode 按题型标签,记录...合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-conversion.md) [0030 串联所有单词的子串](./String/substring
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 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum ...Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ
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 ...
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中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash 2 Add Two Numbers 两数相加 math ...Sorted ...pointers,array ...Merge Two Sorted Lists 合并两个有序链表 lin