0977. Squares of a Sorted Array

977. Squares of a Sorted Array #

题目 #

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:


Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:


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

Note:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

题目大意 #

给一个已经有序的数组,返回的数组也必须是有序的,且数组中的每个元素是由原数组中每个数字的平方得到的。

解题思路 #

这一题由于原数组是有序的,所以要尽量利用这一特点来减少时间复杂度。

最终返回的数组,最后一位,是最大值,这个值应该是由原数组最大值,或者最小值得来的,所以可以从数组的最后一位开始排列最终数组。用 2 个指针分别指向原数组的首尾,分别计算平方值,然后比较两者大小,大的放在最终数组的后面。然后大的一个指针移动。直至两个指针相撞,最终数组就排列完成了。

代码 #


package leetcode

import "sort"

// 解法一
func sortedSquares(A []int) []int {
	ans := make([]int, len(A))
	for i, k, j := 0, len(A)-1, len(ans)-1; i <= j; k-- {
		if A[i]*A[i] > A[j]*A[j] {
			ans[k] = A[i] * A[i]
			i++
		} else {
			ans[k] = A[j] * A[j]
			j--
		}
	}
	return ans
}

// 解法二
func sortedSquares1(A []int) []int {
	for i, value := range A {
		A[i] = value * value
	}
	sort.Ints(A)
	return A
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者