C++解OJ题——合并两个有序数组（每天一个小技巧）

C++解OJ题——合并两个有序数组（每天一个小技巧）

---

原题如下：

  给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
  请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
  注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

---

审题：
  数组本身有序，将两个数组合并为一个数组，合并后的数组依旧要保持有序。合并到nums1数组中，大小已经给定。并且由其解释的信息要求所设计的算法是一个稳定的算法。

代码设计：
  根据题干描述信息可以得出，合并后的数组的最后一个位置的数据是原两个数组中最大的一个数据。而这最大的一个数据来源于两数组有效数据的最后一个的大者。同理倒数第二个位置…
  那我们可以优先将大者依次选出，再依次放到最后。假如有如下的两个数组：

  现有三个指示数组下标的指示指针，如下：

  比较 i 与 j的当前位置元素，将大者放到 k 所指的位置。这样就将大者选出，再选出次大者……

---

代码实现：

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        int i=m-1;//指示数组1有效数据的最后一个数据下标
        int j=n-1;//指示数组2的最后一个数据下标
        int k=m+n-1;//指示数组1的最后一个数据下标
        while(i>=0&&j>=0)//从后往前遍历
        {
            if(nums1[i]>nums2[j])//数组1当前位置大于数组2当前位置
            {
                nums1[k]=nums1[i];//放到k所标识的位置
                k--;i--;//指示指针往前移动一个位置
            }
            else//数组2当前位置大于等于数组1当前位置
            {
                nums1[k]=nums2[j];
                k--;j--;
            }
        }
        while(j>=0)//数组2中还有剩余数据
        {
            nums1[k]=nums2[j];
            k--;j--;
        }
    }
};

  

---

  我是老胡，感谢阅读！！ ❤️ ❤️