Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/977.html
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.
Algorithm 1
This question gives an array in non-descending order, which can have negative numbers. Now let’s find the square of each number, and it is also in non-descending order. If there are only positive numbers in the array, the order of the squared array and the original array is still the same. But if the square of a negative number is a positive number, the order will be disrupted.
The simplest method is to store the square number in a TreeSet, and use its automatic sorting function to get the desired order. Note that you need to use multiset here because there may be duplicate values. See the code below:
Code 1
C++
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
multiset<int> st;
for (int num : A) st.insert(num * num);
return vector<int>(st.begin(), st.end());
}
};
Algorithm 2
If you want to further optimize the time complexity, you can use double pointers to do it, use two variables to point to the beginning and the end, and then compare, each time the square value of the number with the larger absolute value is added to the end of the array first, and then Update one by one, the final result is the requested order, see the code as follows:
Code 2
C++
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int n = A.size(), i = 0, j = n - 1;
vector<int> res(n);
for (int k = n - 1; k >= 0; --k) {
if (abs(A[i]) > abs(A[j])) {
res[k] = A[i] * A[i];
++i;
} else {
res[k] = A[j] * A[j];
--j;
}
}
return res;
}
};
-
class Solution { public int[] sortedSquares(int[] A) { if (A == null || A.length == 0) return A; int length = A.length; int minAbs = Integer.MAX_VALUE; int startIndex = -1; for (int i = 0; i < length; i++) { int num = A[i]; int abs = Math.abs(num); if (abs < minAbs) { minAbs = abs; startIndex = i; } if (num > minAbs) break; } int[] squares = new int[length]; squares[0] = minAbs * minAbs; int index = 1; int index1 = startIndex - 1, index2 = startIndex + 1; while (index1 >= 0 && index2 < length) { if (Math.abs(A[index1]) <= Math.abs(A[index2])) { squares[index] = A[index1] * A[index1]; index1--; } else { squares[index] = A[index2] * A[index2]; index2++; } index++; } while (index1 >= 0) { squares[index] = A[index1] * A[index1]; index++; index1--; } while (index2 < length) { squares[index] = A[index2] * A[index2]; index++; index2++; } return squares; } } ############ class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; for (int i = 0, j = n - 1, k = n - 1; i <= j;) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i]; ++i; } else { res[k--] = nums[j] * nums[j]; --j; } } return res; } } -
// OJ: https://leetcode.com/problems/squares-of-a-sorted-array/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> sortedSquares(vector<int>& A) { int N = A.size(); for (int &n : A) n *= n; vector<int> ans(N); for (int i = 0, j = N - 1, k = N - 1; i <= j; ) { if (A[i] > A[j] ) { ans[k--] = A[i]; ++i; } else { ans[k--] = A[j]; --j; } } return ans; } }; -
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n i, j, k = 0, n - 1, n - 1 while i <= j: if nums[i] * nums[i] > nums[j] * nums[j]: res[k] = nums[i] * nums[i] i += 1 else: res[k] = nums[j] * nums[j] j -= 1 k -= 1 return res ############ # 977. Squares of a Sorted Array # https://leetcode.com/problems/squares-of-a-sorted-array/ class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n i, j, p = 0, n - 1, n - 1 while i <= j: if abs(nums[i]) >= abs(nums[j]): res[p] = nums[i] * nums[i] i += 1 else: res[p] = nums[j] * nums[j] j -= 1 p -= 1 return res -
func sortedSquares(nums []int) []int { n := len(nums) res := make([]int, n) for i, j, k := 0, n-1, n-1; i <= j; { if nums[i]*nums[i] > nums[j]*nums[j] { res[k] = nums[i] * nums[i] i++ } else { res[k] = nums[j] * nums[j] j-- } k-- } return res } -
/** * @param {number[]} nums * @return {number[]} */ var sortedSquares = function (nums) { const n = nums.length; const res = new Array(n); for (let i = 0, j = n - 1, k = n - 1; i <= j; ) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i]; ++i; } else { res[k--] = nums[j] * nums[j]; --j; } } return res; }; -
impl Solution { pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut l = 0; let mut r = n - 1; let mut res = vec![0; n]; for i in (0..n).rev() { let a = nums[l] * nums[l]; let b = nums[r] * nums[r]; if a < b { res[i] = b; r -= 1; } else { res[i] = a; l += 1; } } res } } -
class Solution { /** * @param Integer[] $nums * @return Integer[] */ function sortedSquares($nums) { $i = 0; $j = $k = count($nums) - 1; $rs = array_fill(0, count($nums), -1); while ($i <= $j) { $max1 = $nums[$i] * $nums[$i]; $max2 = $nums[$j] * $nums[$j]; if ($max1 > $max2) { $rs[$k] = $max1; $i++; } else { $rs[$k] = $max2; $j--; } $k--; } return $rs; } }