leetcode|leetcode 88 Merge Sorted Array
【leetcode|leetcode 88 Merge Sorted Array】
Given two sorted integer arrays nums1 and nums2, merge nums2 intonums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal tom + n) to hold additional elements from nums2. The number of elements initialized innums1 and nums2 are m and n respectively.
测试用例：
Runtime Error Message: Last executed input: Input:
[1,2,3,0,0,0], 3, [2,5,6], 3 Output:
[1,2,3,5,6] Expected:
[1,2,2,3,5,6]
错误的解决方案：
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n)
{
set result;
for(int i = 0;
i::iterator iter = result.begin();
for(;
iter!=result.end();
iter++)
{
nums1.push_back(*iter);
}
}
};
我的解决方案：上面就是相同 的元素没装进来，换成multiset就行了
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n)
{
multiset result;
for(int i = 0;
i::iterator iter = result.begin();
for(;
iter!=result.end();
iter++)
{
nums1.push_back(*iter);
}
}
};
简短的解决方案：
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int k = m + n;
while (k-- > 0)
A[k] = (n == 0 || (m > 0 && A[m-1] > B[n-1])) ?A[--m] : B[--n];
}
};
可读性较好：
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int i=m-1;
int j=n-1;
int k = m+n-1;
while(i >=0 && j>=0)
{
if(A[i] > B[j])
A[k--] = A[i--];
else
A[k--] = B[j--];
}
while(j>=0)
A[k--] = B[j--];
}
};
python解决方案：
class Solution:
# @param Aa list of integers
# @param man integer, length of A
# @param Ba list of integers
# @param nan integer, length of B
# @return nothing(void)
def merge(self, A, m, B, n):
x=A[0:m]
y=B[0:n]
x.extend(y)
x.sort()
A[0:m+n]=x
python解决方案2：thats why we love python
def merge(self, A, m, B, n):
A[m:] = B[:n]
A.sort()
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点