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].
Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
Solution
func sortedSquares(nums []int) []int {
length := len(nums)
left, right := 0, length-1
res := make([]int, length)
for pos := length - 1; pos >= 0; pos-- {
if l, r := nums[left]*nums[left], nums[right]*nums[right]; l > r {
res[pos] = l
left++
} else {
res[pos] = r
right--
}
}
return res
}
Description
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
Follow up:
Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?
Solution
func rev(nums []int) {
length := len(nums)
for i, j := 0, length-1; i < length/2; i++ {
nums[i], nums[j-i] = nums[j-i], nums[i]
}
}
func rotate(nums []int, k int) {
k %= len(nums)
rev(nums)
rev(nums[k:])
rev(nums[:k])
}
