LeetCode 求数组的平方后排序（Squares of a Sorted Array）

以你之姓@ 2022-09-05 15:56 23阅读 0赞

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