欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-01 23:32:04
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 ......

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;
    }
};

参考:

(2)解读

参考:

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;
    }
};

参考:

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;
    }
};

参考:

(2)解读

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