目录
88.合并两个有序数组
题目描述
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
时间复杂度O(m+n),空间复杂度O(1)
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1;//指向nums1尾部
int p2 = n - 1;//指向nums2尾部
int current = (int)nums1.size()-1;//指向最末端，从最末端开始放置元素
while (p2>=0) {
//p1>=0（p1结束） && nums1[p1] > nums2[p2] 放置nums1[p1]到当前位置
if (p1>=0 && nums1[p1] > nums2[p2]) {
nums1[current--] = nums1[p1--];
}else{
//p1小于0（p1结束） || nums2[p2] >= nums1[p1] 放置nums2[p2]到当前位置
nums1[current--] = nums2[p2--];
}
}
//p2小于0时，整个过程结束,完成排序
}
};
分析：使用了三个指向不同位置的指针。
75.颜色分类
题目描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目分析
遇到1：跳过，红色指针++
遇到0：跟绿色指针交换值，绿色指针++、红色指针++
遇到2：跟紫色指针交换值，紫色指针–，再次对红色指针的值进行判断
题目实现
时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0;//左侧扫描指针（绿色）
int idx = 0; //当前位置指针（红色）
int right = (int)nums.size()-1;//右侧扫描指针（紫色）
//当idx越过right时，整个过程结束
while (idx<=right) {
int num = nums[idx];
if (num == 0) {
//与left交换后，idx,left都前进一位
//交换后idx不需要再次判断，因为前面的已经扫描过一遍
swichNum(nums, idx++, left++);
}else if(num == 1){
//什么也不做，idx前进一位
idx++;
}else{
//与right交换后，right向左移动一位，
//此时应对idx再次判断,idx可能是0、1、2，所以idx不动，进入下一轮会再次判断
swichNum(nums, idx, right--);
}
}
}
//交换两个元素
void swichNum(vector<int>& nums,int i ,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
16.16.部分排序
题目描述
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
示例：
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]
提示：
0 <= len(array) <= 1000000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sub-sort-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目分析
扫描过的最大值是：8
如果发现当前值小于最大值，记录它的位置（7）
扫描过的最小值是：1
如果发现当前值大于最小值，记录它的位置（1）
题目实现
时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
vector<int> subSort(vector<int>& array) {
if (array.size() == 0) return vector<int>{-1,-1};
int max = array[0]; //记录最大值
int right = -1; //记录最右逆序对的索引
//从左到右寻找最右逆序对
for (int i = 1; i<array.size(); i++) {
int v = array[i];
if (v >= max) {
max = v;
}else{
right = i;
}
}
if (right == -1) return vector<int>{-1,-1};
int min = array[array.size()-1]; //记录最小值
int left = -1; //记录最左逆序对的索引
//从右到左寻找最左逆序对
for (int i = (int)array.size()-2; i>=0; i--) {
int v = array[i];
if (v <= min) {
min = v;
}else{
left = i;
}
}
return vector<int>{left,right};
}
};
977.有序数组的平方
题目描述
给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
//将负数放到一个数组lefts内
int size = (int)A.size();
vector<int> lefts;
for (int i = 0; i<size; i++) {
int v = A[i];
if (v<0) {
lefts.push_back(v);
}else{
break;
}
}
int left = (int)lefts.size()-1;
int right = (int)lefts.size();
int cur = 0;
while (cur<size) {
int leftV = left>=0 ? abs(lefts[left]):INT_MAX;//防止越界
int rightV = right<size?A[right] : INT_MAX;//防止越界
if(rightV < leftV){
A[cur++] = pow(rightV,2);
right++;
}else{
A[cur++] = pow(leftV,2);
left--;
}
}
//left < 0时整个过程结束
return A;
}
};
行者常至，为者常成！