题目描述
示例 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 已按 非递减顺序 排序 code></=>
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题过程
- 方法1
①先将数组内的数平方
②使用快排进行排序
③时间复杂度为O(nlogn)
解题代码
//值的交换
void swap(int *a, int *b){
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
//先写一个快速排序
void quickSort(int *nums, int numsSize ,int begin, int end){
int i, j;
if( begin < end){
i = begin + 1;
j = end;
while(i < j){
if(nums[i] > nums[begin]){
swap(&nums[i], &nums[j]);
j--;
}else{
i++;
}
}
if(nums[i]>=nums[begin]){
i--;
}
swap(&nums[begin],&nums[i]);
quickSort(nums,numsSize,begin,i);
quickSort(nums,numsSize,j,end);
}
}
int* sortedSquares(int* nums, int numsSize, int* returnSize){
for(int i = 0; i < numsSize; i++){
nums[i]= nums[i]*nums[i];
}
quickSort(nums, numsSize, 0, numsSize-1);
*returnSize = numsSize;
return nums;
}
- 方法2
根据原数组就是一个倒序排列的数组，可知，在正数和负数分界处，左边负数的绝对值为从大到小排列，而右边的数为从小到大，故可设置一个新数组，通过比较两个边界的最大值，确定新数组的最大值，往下类推
原数组:-4, -1, 0, 3, 10
绝对值后的数组: 4, 1, 0, 3, 10
平方后的数组: 16, 1, 0, 3, 100
第一次: left right
因为16<100 100 故新数组newnums[4]="100" right往左移 平方后的数组: 16, 1, 0, 3, 第一次: left right 继续16和3比较，挑出最大值 ...... < code></100>
①定义两个数字指针left与right，left指向原数组的最左边下标，right指向最右边的下标
②比较数组在left和right下标对应的值的平方，大的值，存入新数组中，若left值的大，则left需往右移，同理,right需往左移
③循环②直至新数组赋值完毕
解题代码
int Sqrt(int num){
return num*num;
}
//不使用排序 利用双指针实现
int* sortedSquares(int* nums, int numsSize, int* returnSize){
int left = 0, right = numsSize - 1;
int *returnNums = (int *)malloc(sizeof(int)*numsSize);
//定义一个返回数组，并赋予地址
int index = numsSize - 1;
while(index>=0){
if(Sqrt(nums[left]) > Sqrt(nums[right])){
returnNums[index] = Sqrt(nums[left]);
left++;
}
else{
returnNums[index] = Sqrt(nums[right]);
right--;
}
index--;
}
*returnSize = numsSize;
return returnNums;
}
题目描述
给你一个数组，将数组中的元素向右轮转 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 <= 0 1 nums.length <="105" -231 - code></=>
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现代码
- 方法一
两种实现方式：
void rotate(int* nums, int numsSize, int k){
k=k%numsSize;
int tmpNums[numsSize];
for(int i = 0; i < numsSize; i++){
tmpNums[i] = nums[(numsSize-k+i)%numsSize];
}
for(int i=0;i<numssize;i++){ nums[i]="tmpNums[i];" } < code></numssize;i++){>
void rotate(int* nums, int numsSize, int k){
k = k % numsSize;
if(k == 0){
return;
}
int *tmpNums = malloc(sizeof(int)*k);
for(int i = 0; i < k; i++){
tmpNums[i] = nums[numsSize-i-1];
}
for(int j = numsSize-1; j >= 0; j--){
if(j >= k){
nums[j] = nums[j -k];
}
else{
nums[j] = tmpNums[k -j-1];
}
}
}
Original: https://www.cnblogs.com/jane315/p/15941215.html
Author: jane_315
Title: leecode每日刷题1
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583740/
转载文章受原作者版权保护。转载请注明原作者出处！