做海外房产最好的网站,购物商城平台开发,科技公司名称大全简单大气,seo网络推广优势目录 一、题目
二、分析
2.1 暴力求解法
2.2 找规律
2.3 追求时间效率#xff0c;以空间换时间
三、结论 一、题目 给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3
输出…目录 一、题目
二、分析
2.1 暴力求解法
2.2 找规律
2.3 追求时间效率以空间换时间
三、结论 一、题目 给定一个整数数组 nums将数组中的元素向右轮转 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] 二、分析
2.1 暴力求解法
这题是旋转字符串但是它的实质是将前面n-1个数据往后移一位然后将最后一个数据移到第一个旋转几次则执行几次这个步骤。为了变量不被覆盖变量采取从后向前移动而最后一个数据利用一个空变量temp去拷贝一份在前面数据移动完成后则拷贝到第一个数据。如下面代码
void rotate(int* num ,int k , int size)
{k % size;//size次一次循环while (k){int temp num[size-1];for (int i size-1; i 0; i--){num[i] num[i - 1];}num[0] temp;k--;}
}int main()
{int arr[] { 7,1,2,3,4,5,6 };int size sizeof(arr) / sizeof(arr[0]);int k 1;printf(旋转几次数组:);scanf(%d, k);printf(旋转前);for (int i 0; i size; i){printf(%d , arr[i]);}rotate(arr, k, size);printf(\n旋转后为);for (int i 0; i size; i){printf(%d , arr[i]);}return 0;
} 2.2 找规律
我们发现暴力求解虽然可以解出此题但是时间复杂度那我们有什么办法去降低时间复杂度呢我们可以尝试降低它的循环次数找找看他们有什么规律
如图将前面n-k个数字逆置然后将后面n个逆置然后将他们整体逆置。红色位将要进行逆置的数 代码如下 void Inversion(int* arr, int l, int r)
{while (l r){int temp arr[l];arr[l] arr[r];arr[r] temp;l;r--;}
}void rotate(int* nums, int numsSize, int k) {k % numsSize;//不让数组越界完成一次数组长度的旋转数组不变Inversion(nums, 0, numsSize - k - 1);Inversion(nums, numsSize - k, numsSize - 1);Inversion(nums, 0, numsSize - 1);
}int main()
{int arr[] { 7,1,2,3,4,5,6 };int size sizeof(arr) / sizeof(arr[0]);int k 1;printf(旋转几次数组:);scanf(%d, k);printf(旋转前);for (int i 0; i size; i){printf(%d , arr[i]);}rotate(arr, size, k);printf(\n旋转后为);for (int i 0; i size; i){printf(%d , arr[i]);}return 0;
}
*这里要注意数组越界访问我们发现数组完成一次数组长度的旋转数组不变所以我们取模于数组长度。 2.3 追求时间效率以空间换时间
这里我们不讨论空间复杂度只优化时间复杂度所以我们可以新开辟一段空间将后n个旋转的数字先放入我们开辟的空间然后再将前面的n-k个数字放入空间后面。
如代码
void rotate(int* nums, int numsSize, int k) {k % numsSize;int* temp (int*)malloc(sizeof(int) * numsSize);memcpy(temp, nums numsSize - k, sizeof(int) * k);memcpy(temp k, nums, sizeof(int) * (numsSize - k));memcpy(nums, temp, sizeof(int) * numsSize);free(temp);//释放临时空间temp NULL;
}int main()
{int arr[] { 7,1,2,3,4,5,6 };int size sizeof(arr) / sizeof(arr[0]);int k 1;printf(旋转几次数组:);scanf(%d, k);printf(旋转前);for (int i 0; i size; i){printf(%d , arr[i]);}rotate(arr, size, k);printf(\n旋转后为);for (int i 0; i size; i){printf(%d , arr[i]);}return 0;
} 三、结论
每一道题都有属于自己的空间和时间复杂度当你写出一段代码的时候去想想还能不能继续去优化它使它的时间和空间复杂度更小。姜糖在这里就是不断在优化它的时间复杂度从O(N^2)到最后的O(N)。如果大家还有什么不同的看法可以跟姜糖展开讨论哦。
