当前位置:网站首页>Leetcode daily practice: rotating arrays
Leetcode daily practice: rotating arrays
2022-07-05 17:48:00 【Sharp blade CC】
link : Rotated array
Ask us to transfer , Is to move the last number to the front , Then keep the other numbers in order and move one step back .
Conventional thinking : Just use while loop , The title requires us to rotate n Time , We'll be back n Move the numbers to the front . Although this idea works , But think about it , Move the front number back each time , This time complexity is not low , So we won't talk about this conventional idea here .
New ideas : The title requires us to rotate the array , In fact, we can First flip the entire array in order , then Before we move on n - 1 Number reversal order , Finally, after numsSize - n Number reversal order ( Suppose the number of arrays here is numsSize individual ), In fact, the array rotation is completed .
notes : Here's a key point , Namely If you flip n Time , and n Equal to the length of the array numsSize Words , In fact, the original array does not move , And so on , So we can n Do something about it .
And the spatial complexity of this idea is O(1) Of !
Code :
void partRotate(int* a, int left, int right)
{
// Use left and right pointers
while(left < right)
{
int tmp = a[left];
a[left] = a[right];
a[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k){
k %= numsSize;
// if k The finished length of the die is 0, Then there is no need to rotate
if(k == 0)
return;
partRotate(nums, 0, numsSize - 1);// First flip the entire array
partRotate(nums, 0, k - 1);// Then flip the front k - 1 individual
partRotate(nums, k, numsSize - 1);// Finally, after turning numsSize - k individual
}
边栏推荐
猜你喜欢
flask接口响应中的中文乱码(unicode)处理
企业数字化发展中的六个安全陋习,每一个都很危险!
ICML 2022 | meta proposes a robust multi-objective Bayesian optimization method to effectively deal with input noise
Knowledge points of MySQL (6)
2022新版PMP考试有哪些变化?
Server configuration jupyter environment
Ten top automation and orchestration tools
PMP认证需具备哪些条件啊?费用多少啊?
Cmake tutorial Step2 (add Library)
ELK日志分析系统
随机推荐
如何保存训练好的神经网络模型(pytorch版本)
tkinter窗口预加载
ICML 2022 | meta proposes a robust multi-objective Bayesian optimization method to effectively deal with input noise
ICML 2022 | Meta提出魯棒的多目標貝葉斯優化方法,有效應對輸入噪聲
Server configuration jupyter environment
独立开发,不失为程序员的一条出路
一文读懂简单查询代价估算
Rider set the highlighted side of the selected word, remove the warning and suggest highlighting
Sentinel flow guard
C # realizes crystal report binding data and printing 3-qr code barcode
Tita performance treasure: how to prepare for the mid year examination?
Six bad safety habits in the development of enterprise digitalization, each of which is very dangerous!
漫画:一道数学题引发的血案
Cartoon: a bloody case caused by a math problem
论文阅读_中文NLP_LTP
VBA drives SAP GUI to realize office automation (II): judge whether elements exist
十个顶级自动化和编排工具
Cartoon: looking for the k-th element of an unordered array (Revised)
Is it safe to open an account online? What is the general interest rate of securities financing?
Anaconda中配置PyTorch环境——win10系统(小白包会)