有序数组的平方
题目
给你一个按 非递减顺序 排序的整数数组 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] <= 104
nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
思路
思路1 暴力解题：对数组进行平方运算，再对数组进行排序，返回数组。
思路2 双指针解题：因为数组为有序数组，平方之后最大值在最左端或最右端，可以考虑使用双指针，即设置两个指针分别指向数组的起始位置和终止位置；定义一个新数组用来存储结果，同时设置一个指针指向其终止位置。
代码实现
暴力解题
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i=0;i<nums.length;i++){
nums[i]=nums[i]*nums[i];
}
for(int j=0;j<nums.length;j++){
for(int k=j+1;k<nums.length;k++){
int temp;
if(nums[j]>nums[k]){
temp=nums[j];
nums[j]=nums[k];
nums[k]=temp;
}
}
}
return nums;
}
}
双指针解法
class Solution {
public int[] sortedSquares(int[] nums) {
int head=0;
int tail=nums.length-1;
int[] result=new int[nums.length];
int index=result.length-1;
while(head<=tail){
if(nums[head]*nums[head]>nums[tail]*nums[tail]){
result[index]=nums[head]*nums[head];
index--;
head++;
}else{
result[index]=nums[tail]*nums[tail];
index--;
tail--;
}
}
return result;
}
}
轮转数组
题目
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
例1：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
例2：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
代码实现
public void rotate(int[] nums, int k) {
int len = nums.length;
int[] arr = new int[len];
for(int i = 0;i < len;i++){
arr[(i + k)%len] = nums[i];
}
for(int i = 0;i < len;i++){
nums[i] = arr[i];
}
}
|