利用双指针思想解决有序数组的平方排序问题

Question

当前存在一个以非递减顺序排序的整数数组nums，编写算法返回每个数字的平方所组成的新数组，且同样按照非递减顺序排序。

本题最简单的思路即对每个数组元素均平方后的数组进行再排序，其时间复杂度为。但由题意可知，有序数组最左端与最右端的元素在平方后均有可能成为最大数，因此可以考虑采用双指针法分别对数组中的负数与正数进行处理。

以数列[-7, -3, 2, 3, 11]为例，首先定义两个指针，其中负数指针low指向nums数组起始位置（即最小值位置），正数指针high指向nums数组末尾位置（即最大值位置）。再定义一个辅助新数组result生成的索引指针index，并指向result数组的末尾位置。

1 2	int* result = malloc(sizeof(int) * numsSize); int low = 0, high = numsSize - 1, index = numsSize - 1;

当high所指元素的平方结果大于low所指元素的平方结果时，将high所指元素的平方结果导入result中index所指位置。同时，high左移至nums的下一位并准备与当前low所指元素进行比较，index左移至result的下一位。

1
2
3

if(nums[low] * nums[low] < nums[high] * nums[high]){
  result[index--] = nums[high] * nums[high--];
}

当low所指元素的平方结果大于high所指元素的平方结果时，将low所指元素的平方结果导入result中index所指位置。同时，low右移至nums的下一位并准备与当前high所指元素进行比较，index左移至result的下一位。

1
2
3

if(nums[low] * nums[low] > nums[high] * nums[high]){
  result[index--] = nums[low] * nums[low++];
}

故最终完整代码为

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int* result = malloc(sizeof(int) * numsSize);
    int low = 0, high = numsSize - 1, index = numsSize - 1;
    while(low <= high){
        if(nums[low] * nums[low] < nums[high] * nums[high]){
            result[index--] = nums[high] * nums[high--];
        }
        else{
            result[index--] = nums[low] * nums[low++];
        }
    }
    *returnSize = numsSize;
    return result;
}

Python下代码为

1
2
3

class Solution(object):
    def sortedSquares(self, nums):
        return sorted([i**2 for i in nums])