class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
}
};
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 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] <= 104nums 已按 非递减顺序 排序
进阶：
O(n) 的算法解决本问题原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 46.4 MB, 提交时间: 2024-09-08 09:37:40
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
int i = 0;
int j = n - 1;
for (int p = n - 1; p >= 0; p--) {
int x = nums[i];
int y = nums[j];
if (-x > y) {
ans[p] = x * x;
i++;
} else {
ans[p] = y * y;
j--;
}
}
return ans;
}
}
rust 解法, 执行用时: 8 ms, 内存消耗: 2.2 MB, 提交时间: 2024-09-08 09:37:06
impl Solution {
pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![0; n];
let mut i = 0;
let mut j = n - 1;
for p in (0..n).rev() {
let x = nums[i];
let y = nums[j];
if -x > y {
ans[p] = x * x;
i += 1;
} else {
ans[p] = y * y;
j -= 1;
}
}
ans
}
}
cpp 解法, 执行用时: 19 ms, 内存消耗: 28 MB, 提交时间: 2024-09-08 09:36:52
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
int i = 0, j = n - 1;
for (int p = n - 1; p >= 0; p--) {
int x = nums[i], y = nums[j];
if (-x > y) {
ans[p] = x * x;
i++;
} else {
ans[p] = y * y;
j--;
}
}
return ans;
}
};
javascript 解法, 执行用时: 96 ms, 内存消耗: 56.9 MB, 提交时间: 2024-09-08 09:36:35
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
const n = nums.length;
const ans = Array(n);
let i = 0, j = n - 1;
for (let p = n - 1; p >= 0; p--) {
const x = nums[i], y = nums[j];
if (-x > y) {
ans[p] = x * x;
i++;
} else {
ans[p] = y * y;
j--;
}
}
return ans;
};
python3 解法, 执行用时: 58 ms, 内存消耗: 18.1 MB, 提交时间: 2024-09-08 09:36:16
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
i, j = 0, n - 1
for p in range(n - 1, -1, -1):
x, y = nums[i], nums[j]
if -x > y:
ans[p] = x * x
i += 1
else:
ans[p] = y * y
j -= 1
return ans
golang 解法, 执行用时: 28 ms, 内存消耗: 6.8 MB, 提交时间: 2021-07-13 07:51:45
func sortedSquares(nums []int) []int {
n := len(nums)
ans := make([]int, n)
i, j := 0, n-1
for pos := n - 1; pos >= 0; pos-- {
if v, w := nums[i]*nums[i], nums[j]*nums[j]; v > w {
ans[pos] = v
i++
} else {
ans[pos] = w
j--
}
}
return ans
}
golang 解法, 执行用时: 40 ms, 内存消耗: 6.8 MB, 提交时间: 2021-06-10 14:50:37
func sortedSquares(nums []int) []int {
sort.Slice(nums, func(i, j int) bool {
if abs(nums[i]) < abs(nums[j]) {
return true
}
return false
})
for i, num := range nums {
nums[i] = num * num
}
return nums
}
func abs(i int) int {
if i < 0 {
return -i
}
return i
}