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; } };
参考:
(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。
参考:
推荐阅读
-
Leetcode No.88 Merge Sorted Array(c++实现)
-
Leetcode No.26 Remove Duplicates from Sorted Array(c++实现)
-
Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现)
-
Merge K Sorted List Leetcode #23 题解[C++]
-
【LeetCode】80. Remove Duplicates from Sorted Array II (删除排序数组中的重复项 II)-C++实现及详细图解
-
【LeetCode】26. Remove Duplicates from Sorted Array (删除排序数组中的重复项)-C++实现的两种方法
-
Leetcode No.88 Merge Sorted Array(c++实现)
-
Leetcode No.26 Remove Duplicates from Sorted Array(c++实现)
-
Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现)