977. 有序数组的平方

leecode原题

题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序

示例

示例 1:

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2:

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶

请你设计时间复杂度为 O(n) 的算法解决本问题

解题思路

前提: 这是一个有序数组, 只是数组中的元素可能是负值

1. 暴力破解法

我们第一个想到的可能就是暴力破解法, 即第一步: 先对数组元素进行平方，第二步: 使用相关的排序方法进行排序。如果整体的时间复杂度即为(O(第一步)+0(第二步)), 如果是第二步是快排，那么整体时间复杂度即为(O(n+nlogn)).

2. 双指针法

最关键的一个点就是: 一个数组的每个元素的平方的最大值只能是在数组的两端取到，比如[-6, -3, -2, 0, 2, 5]。那么我们就转变 一个思路就是分别从数组左端和右端依次比较，寻找其中最大值。

实现方法(双指针法): 分别定义两个指针left_index=0, right_index=len(arr)-1, 以及一个变量k=len(arr)-1, 目标数组dest_arr=make([]int, len(arr)-1), 然后比较sqrt(arr[left_index])和sqrt(arr[right_index]), 然后将其中最大值插入到dest_arr[k]中，然后k-=1, 相应的left_index+=1或者right_index-=1, 直到left_index碰到rigth_index。

实现

1. 暴力破解法

算法很简单，这里就不实现了。

2. 双指针法

源码

func sortedSquares(nums []int) []int {
    size := len(nums)
    left_index := 0
    right_index := size - 1
    k := size - 1
    dest_arr := make([]int, size)

    for left_index <= right_index {
        left_sqrt := nums[left_index] * nums[left_index]
        right_sqrt := nums[right_index] * nums[right_index]
        if left_sqrt < right_sqrt {
            dest_arr[k] = right_sqrt
            right_index -= 1
        } else {
            dest_arr[k] = left_sqrt
            left_index += 1
        }
        k -= 1
    }
    return dest_arr
}