【数组】面试题 10.01. 合并排序的数组

水深无声 2022-11-25 00:48 158阅读 0赞

> ☞梦想进大厂的一只程序猿☜  
> ☞期望毕业前力扣刷够400题☜
> 
> ☞正在复习数据结构和算法☜
> 
> ☞博客地址：[https://www.huangliangshuai.com/][https_www.huangliangshuai.com]☜

# 1. 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 2. 题目分析 #

1.  第一个方法，借用O（m）的空间，将A数组的数字转移到新开辟的空间中，然后依次的比较，方放入A数组中
2.  第二个方法，我们可以想想可以不借用空间的方法来解决这个问题，我们可以看到，两个数组的数字都是排序（升序）好的，我们可以从后往前遍历，也就是让A数组max与B数组max比较，去最大的一个排在最后，依次判断

# 3 题目代码 #

class Solution {
        
        public void merge(int[] A, int m, int[] B, int n) {
        
                int left = m - 1;
                int right = n - 1;
                int index = m + n - 1;
                while(left >= 0 && right >= 0){
        
                if(A[left] >= B[right]){
        
                    A[index--] = A[left--];
                }else{
        
                    A[index--] = B[right--];
                }
            }
            while(left >= 0){
        
                A[index--] = A[left--];
            }
            while(right >= 0){
        
                 A[index--] = B[right--];
            }
        }
    }

[https_www.huangliangshuai.com]: https://www.huangliangshuai.com/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221124/b385008bf8d04d3b871405587a5688b9.png