今天这一题和昨天的知识点是一样的,就是双指针法
。
题目:
给你一个按 非递减顺序 排序的整数数组 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
已按 非递减顺序 排序
刚开始我的思路:
func sortedSquares(nums []int) []int {f, r := 0, len(nums)-1var arr = []int{}for f <= r {ones := nums[r] * nums[r]twos := nums[f] * nums[f]if ones <= twos {arr = insertHead(arr, twos)f++} else {arr = insertHead(arr, ones)r--}}return arr
}func insertHead(arr []int, n int) []int {arr = append([]int{n}, arr...)return arr
}
结果时间复杂度O(n²),因为头插需要O(n)。
代码随想录中有O(log(n))的解法,有兴趣的可以去看看。
链接放这里了:代码随想录 (programmercarl.com)
不过咱们还是直接看O(n)的算法实现吧。
// 双指针
func sortedSquares(nums []int) []int {Len := len(nums)f, r := 0, Len-1arr := make([]int, Len)k := rfor k >= 0 {ones := nums[r] * nums[r]twos := nums[f] * nums[f]if ones >= twos {arr[k] = onesr--} else {arr[k] = twosf++}k--}return arr
}
从两头开始标记,指针平方大的先复制再往里走,直到所有值赋完。