LeetCode-Merge Sorted Array

本来感觉题目很简单,只要根据题意写出来即可。但是写的过程中出了很多 Bug。这些 Bug 主要由没有分析清楚指针指向哪里导致,由于 i 和 j 两个指针都是动态的,所以需要想清楚再写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i=0,j=0;
while(j<n){
if(i<m+j && nums2[j]<nums1[i]){
for(int k=m+j-1;k>=i;k--){
nums1[k+1]=nums1[k];
}
nums1[i]=nums2[j++];
}
if(i==m+j || m==0)
nums1[i]=nums2[j++];
i++;
}
}
}

运行效率不是很理想,只超过了不到 10%的人。

我觉得一个可以优化的方向是暂存 nums2 中每个数字应该插入的位置,只移动一次 nums1。但是看了别人的思路以后,觉得我的这个思路依旧很蠢。别人的思路都是从右向前直接将数字填入 nums1,避免了多次移动元素的尴尬。下面是我根据这个思路写的一个版本:

1
2
3
4
5
6
7
8
9
10
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
while(n>0){
if(m>0)
nums1[m+n-1]=nums1[m-1]>nums2[n-1]?nums1[--m]:nums2[--n];
else
nums1[m+n-1]=nums2[--n];
}
}
}