[数据结构与算法]LeetCode 求数组的平方后排序（Squares of a Sorted Array）

LeetCode 求数组的平方后排序（Squares of a Sorted Array）不使用容器自带排序

题目描述

给定一个按非降序排序的整数数组 nums，返回一个按非降序排序的每个数字的平方数组。

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

思路

因为原数组是按照从小到大的顺序进行排列的，所以首先找到原数组当中第一个大于0的数字，如果没有，说明原数组全部小于0，此时只需要从后往前遍历数组，进行平方放入结果当中即可。如果有，判断第一个大于0的数字的位置，如果是第一个数字，说明所有的数字都大于0，只要从前往后遍历数组进行平方放入结果当中即可。接下来是最普遍的情况：
如果第一个大于0的数字下标不等于0，比较其与其左边的数的平方大小，如果比左边的小，则原数组中平方最小的数为其左边那个数。将minIndex重新赋值。之后就将原数组分给为两个部分，平方进行比较赋值即可。

class Solution {
public:
	vector<int> sortedSquares(vector<int>& nums) {
		vector<int> res;
		//先找到数组当中0的位置
		int minIndex = -1;
		for (int i = 0; i < nums.size(); i++)
		{
			if (nums[i] >= 0)
			{
				minIndex = i;
				break;
			}
		}

		//如果第一个就是最小值,那么直接计算返回即可
		if (minIndex == 0)
		{
			for (int i = 0; i < nums.size(); i++)
			{
				res.push_back(nums[i] * nums[i]);
			}
		}
		//没有一个大于0的
		else if (minIndex == -1)
		{
			for (int i = nums.size() - 1; i >= 0; i--)
			{
				res.push_back(nums[i] * nums[i]);
			}
		}
		//如果不是，分为两个
		else
		{
			if (nums[minIndex] * nums[minIndex] > nums[minIndex - 1] * nums[minIndex - 1])
			{

				minIndex = minIndex - 1;
			}
			res.push_back(nums[minIndex] * nums[minIndex]);
			int leftHigh = minIndex - 1;
			int rightLow = minIndex + 1;
			while (leftHigh >= 0 && rightLow < nums.size())
			{
				if (nums[leftHigh] * nums[leftHigh] < nums[rightLow] * nums[rightLow])
				{
					res.push_back(nums[leftHigh] * nums[leftHigh]);
					leftHigh--;
				}
				else
				{
					res.push_back(nums[rightLow] * nums[rightLow]);
					rightLow++;
				}
			}
			while (leftHigh >= 0)
			{
				res.push_back(nums[leftHigh] * nums[leftHigh]);
				leftHigh--;
			}
			while (rightLow < nums.size())
			{
				res.push_back(nums[rightLow] * nums[rightLow]);
				rightLow++;
			}

		}
		return res;

	}
};