Leetcode No.88 Merge Sorted Array(c++实现）

1. 题目

1.1 英文题目

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

1.2 中文题目

给定两个排序整数数组nums1和nums2，将nums2合并为一个排序数组nums1。

nums1和nums2中初始化的元素数量分别为m和n。假设nums1有足够的空间(大小大于或等于m + n)来容纳nums2中的其他元素。

1.3输入输出

输入	输出
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3	[1,2,2,3,5,6]
nums1 = [1], m = 1, nums2 = [], n = 0	[1]
nums1 = [0], m = 0, nums2 = [1], n = 1	[1]

1.4 约束条件

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

2. 实验平台

IDE：VS2019
IDE版本：16.10.1
语言：c++11

3. 程序

3.1 测试程序

#include "Solution.h"
#include <vector>	// std::vector
#include<iostream>	// std::cout
using namespace std;

// 主程序
void main()
{
	// 输入
	vector<int> digits = { 9,9,9 };

	Solution solution; // 实例化Solution
	vector<int> output = solution.plusOne(digits); // 主功能

	// 输出
	for (auto i : output)
		cout << i;
}

3.2 功能程序

3.2.1 最优算法

（1）代码

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) 
    {
        int carry = 1; // 存放进位数字
        int length = digits.size(); 
        for (int i = length - 1; i >= 0; --i) 
        {
            // 若某一位没有上一位的进位，则再高位都不会再有进位，也就是说高位都保持不变，可以直接返回结果
            if (carry == 0) return digits; 

            // 若有进位，则需要计算进位值及其当前位数字，也就是需要进行循环
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }

        // 若是最高位还需要进位，则需要在最高位插入"1"
        if (carry == 1) digits.insert(digits.begin(), 1);
        return digits;
    }
};

参考：https://www.cnblogs.com/grandyang/p/4079357.html

（2）解读

参考：
https://blog.csdn.net/linhuanmars/article/details/22365957
https://blog.csdn.net/Tianc666/article/details/105769411

3.2.2 直观求解法

（1）代码1

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> digitsNew(digits.size() + 1);//新数字(逆序）
        int count = 1;//进位（0/1)
        for (int i = 0; i < digits.size(); i++)
        {
            int tempOrder = digits.size() - 1 - i;
            int sumTemp = digits[tempOrder] + count;
            count = sumTemp / 10;
            digitsNew[i] = sumTemp % 10;+
            if (i == digits.size() - 1)
                digitsNew[i + 1] = count;
        }

        // 逆序转正序
        int length = digits.size() + digitsNew.back();
        vector<int> digitsFinal(length);
        for (int i = length - 1; i >= 0; i--)
            digitsFinal[i] = digitsNew[length - 1 - i];
        return digitsFinal;
    }
};

（2）思路

先逆转求值，再逆转过来。但是我的代码写法不太简洁，可以参考代码2

（3）代码2

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution 
{
public:
    vector<int> plusOne(vector<int> &digits) 
    {
        vector<int> ret(digits);
        reverse(ret.begin(), ret.end());

        int flag = 1;
        for(int i = 0; i < ret.size(); i++)
        {
            ret[i] += flag;
            //这里的flag的结果要么是0，要么是1
            flag = ret[i] / 10;
            ret[i] %= 10; 
        }

        if (flag == 1)
            ret.push_back(1);

        reverse(ret.begin(), ret.end());

        return ret;
    }
};

参考：https://theonegis.blog.csdn.net/article/details/44258329

3.2.3 其他算法

（1）代码

#pragma once
#include<vector>    // std::vector
//#include<limits.h>  // INT_MIN整型最小值
#include<algorithm> // std::max
using namespace std;

//主功能
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] == 9) digits[i] = 0;
            else {
                digits[i] += 1;
                return digits;
            }
        }
        if (digits.front() == 0) digits.insert(digits.begin(), 1);
        return digits;
    }
};

参考：https://www.cnblogs.com/grandyang/p/4079357.html

（2）解读

将一个数字的每个位上的数字分别存到一个一维向量中，最高位在最开头，我们需要给这个数字加一，即在末尾数字加一，如果末尾数字是9，那么则会有进位问题，而如果前面位上的数字仍为9，则需要继续向前进位。具体算法如下：首先判断最后一位是否为9，若不是，直接加一返回，若是，则该位赋0，再继续查前一位，同样的方法，知道查完第一位。如果第一位原本为9，加一后会产生新的一位，那么最后要做的是，查运算完的第一位是否为0，如果是，则在最前头加一个1。
参考：https://www.cnblogs.com/grandyang/p/4079357.html