leetcode_merge_sorted_array

发表于

难度：Medium

解题思路：从前往后进行重新排序会有问题。

5 7        i指向5
1 4 6    j指向1

第一次调换后
1 7        i指向7
5 4 6    但此时这个数组已经无序

考虑别的思路，从后往前排序，先找最大的。
代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int reverse_nums1_index = m-1, reverse_nums2_index = n-1,reverse_final_index=m+n-1;
        while(reverse_nums1_index >=0 && reverse_nums2_index >= 0 && reverse_final_index >= 0)
        {
            if(nums1[reverse_nums1_index] <= nums2[reverse_nums2_index])
            {
                nums1[reverse_final_index--]=nums2[reverse_nums2_index--];
            }
            else
            {
                nums1[reverse_final_index--]=nums1[reverse_nums1_index--];
            }
        }
        while(reverse_nums1_index >=0)
        {
            nums1[reverse_final_index--]=nums1[reverse_nums1_index--];
        }
        while(reverse_nums2_index >=0)
        {
            nums1[reverse_final_index--]=nums2[reverse_nums2_index--];
        }
    }
};

运行结果：3ms，超过33.85%。