首页 > 代码库 > 数组旋转
数组旋转
问题：
返回将一维数组向右旋转K个位置的结果。比如，一维数组{1,2,3,4,5}，k=2时，返回结果是{4,5,1,2,3}。要求常数级空间复杂度，允许修改原有数组
看到一个比较巧妙的方法，将数组反转三次，第一次反转整个数组，第二次反转数组的前K个数，第三次反转数组剩下的数。
每次反转的时间为O(N)。
例如，
一维数组{1,2,3,4,5},k=2
第一次反转：5,4,3,2,1
第二次反转：4,5,3,2,1
第三次反转：4,5,1,2,3 即为最终结果
代码入下：
int[] rotateK(int[] A,int k){ if(A==null || k>=A.length) return A; reverse(A,0,A.length-1); //反转整个数组 reverse(A,0,A.length-1); //反转前K个数 reverse(A,0,A.length-1); //反转剩下的数 return A; } void reverse(int[] A,int start,int end){ while(start<end){ int temp = A[start]; A[start] = A[end]; A[start] = temp; start++; end--; } }
数组旋转
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。