力扣链接：977. 有序数组的平方，难度：简单。
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
进阶：请你设计时间复杂度为 O(n) 的算法解决本问题。
示例 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 <= 10^4-10^4 <= nums[i] <= 10^4nums已按 非递减顺序 排序
思路
- 数组中最小的数位于数组内部，需要遍历才能找到，不太方便。
但如果反向思考，能否更加方便地优先处理另外一些数呢？那么优先处理哪些数呢？
点击查看答案
答案是优先处理数组两端的数，因为它们最大。
复杂度
时间复杂度
O(N)
空间复杂度
O(N)
Java #
class Solution {
public int[] sortedSquares(int[] nums) {
var results = new int[nums.length];
var left = 0;
var right = nums.length - 1;
var index = right;
while (left <= right) {
if (Math.abs(nums[left]) <= nums[right]) {
results[index] = nums[right] * nums[right];
right -= 1;
} else {
results[index] = nums[left] * nums[left];
left += 1;
}
index -= 1;
}
return results;
}
}
Python #
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
results = [None] * len(nums)
left = 0
right = index = len(nums) - 1
while left <= right:
if abs(nums[left]) <= nums[right]:
results[index] = nums[right] ** 2
right -= 1
else:
results[index] = nums[left] ** 2
left += 1
index -= 1
return results
C++ #
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
auto results = vector<int>(nums.size());
auto left = 0;
int right = nums.size() - 1; // Should not use 'auto' here because 'auto' will make this variable become `unsigned long` which has no `-1`.
auto index = right;
while (left <= right) {
if (abs(nums[left]) <= nums[right]) {
results[index] = nums[right] * nums[right];
right -= 1;
} else {
results[index] = nums[left] * nums[left];
left += 1;
}
index -= 1;
}
return results;
}
};
JavaScript #
var sortedSquares = function (nums) {
const results = Array(nums.length).fill(null)
let left = 0
let right = nums.length - 1
let index = right
while (left <= right) {
if (Math.abs(nums[left]) <= nums[right]) {
results[index] = nums[right] * nums[right]
right -= 1
} else {
results[index] = nums[left] * nums[left]
left += 1
}
index -= 1
}
return results
};
C# #
public class Solution
{
public int[] SortedSquares(int[] nums)
{
var results = new int[nums.Length];
int left = 0;
int right = nums.Length - 1;
int index = right;
while (left <= right)
{
if (Math.Abs(nums[left]) <= nums[right])
{
results[index] = nums[right] * nums[right];
right -= 1;
}
else
{
results[index] = nums[left] * nums[left];
left += 1;
}
index -= 1;
}
return results;
}
}
Go #
func sortedSquares(nums []int) []int {
results := make([]int, len(nums))
left := 0
right := len(nums) - 1
index := right
for left <= right {
if math.Abs(float64(nums[left])) <= float64(nums[right]) {
results[index] = nums[right] * nums[right]
right -= 1
} else {
results[index] = nums[left] * nums[left]
left += 1
}
index -= 1
}
return results
}
Ruby #
def sorted_squares(nums)
results = Array.new(nums.length)
left = 0
right = nums.size - 1
index = right
while left <= right
if nums[left].abs <= nums[right]
results[index] = nums[right] * nums[right]
right -= 1
else
results[index] = nums[left] * nums[left]
left += 1
end
index -= 1
end
results
end
其它语言
欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 977. 有序数组的平方。题解2的思路：使用 `sort()`
复杂度
时间复杂度
O(N * log N)
空间复杂度
O(N)
Java #
class Solution {
public int[] sortedSquares(int[] nums) {
for (var i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
Arrays.sort(nums);
return nums;
}
}
Python #
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
results = [num ** 2 for num in nums]
results.sort()
return results
C++ #
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for (auto i = 0; i < nums.size(); i++) {
nums[i] *= nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};
JavaScript #
var sortedSquares = function (nums) {
return _.sortBy(
nums.map((num) => num * num)
)
};
C# #
public class Solution
{
public int[] SortedSquares(int[] nums)
{
for (int i = 0; i < nums.Length; i++)
nums[i] *= nums[i];
Array.Sort(nums);
return nums;
}
}
Go #
func sortedSquares(nums []int) []int {
for i, _ := range nums {
nums[i] *= nums[i]
}
sort.Sort(sort.IntSlice(nums))
return nums
}
Ruby #
def sorted_squares(nums)
nums.map { |num| num ** 2 }.sort
end