一、第一种方法,都想得到的。
static int[] LeftShift1(int[] arr,int K){//K为循环左移位数
int N=arr.length;
int[] new_arr=new int[N]; //新开一个数组,空间复杂度O(n)
for(int i = 0; i <N; i++)
new_arr[i] = arr[(K+i)%N ];
return new_arr;
}
二、利用“翻转”完成优化,《编程之美》上的算法
考虑一下数组A中元素1234567循环左移2位到底是怎么个情况!!!将数组A分成两个部分:A[0~k-1] 和 A[k~n-1] ,(12与34567)将这两个部分分别翻转,然后放在一起在翻转(逆序)。具体是这样的:
(1)翻转12:12 ---> 21
(2)翻转34567: 34567 ---> 76543
(3)一起翻转2176543:2176543 --->3456712
//翻转b~e
static void Reverse(int[] arr, int b, int e){
while(b < e){
int temp = arr[e]; //只需新开一个辅助空间
arr[e] = arr[b];
arr[b] = temp;
b++;
e--;
}
}
//左移K位
static void LeftShift(int[] arr, int K){
int N=arr.length;
//如果K>N,取K=K%N。
K %= N;
Reverse(arr, 0, K - 1);
Reverse(arr, K, N - 1);
Reverse(arr, 0, N - 1);
}
第一种算法有O(n)的空间复杂度,第二种有O(1)的空间复杂度,两种算法时间复杂度同为O(n)。
测试程序:
public class Test{
//方法一
static int[] LeftShift1(int[] arr,int K){//K为循环左移位数
int N=arr.length;
int[] new_arr=new int[N];
for(int i = 0; i <N; i++)
new_arr[i] = arr[(K+i)%N ];
return new_arr;
}
static void print(int[] arr){
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
//翻转b~e
static void Reverse(int[] arr, int b, int e){
while(b < e){
int temp = arr[e];
arr[e] = arr[b];
arr[b] = temp;
b++;
e--;
}
}
//方法二
static void LeftShift(int[] arr, int K){
int N=arr.length;
K %= N;
Reverse(arr, 0, K - 1);
Reverse(arr, K, N - 1);
Reverse(arr, 0, N - 1);
}
public static void main(String[] args){
int[] a={1,2,3,4,5,6,7};
print(a);
int[] new_arr = LeftShift1(a,2);
print(new_arr);
// Reverse(a,2,5);
LeftShift(a, 4);
print(a);
}
}
运行:
C:\ex>java Test
1 2 3 4 5 6 7
3 4 5 6 7 1 2
5 6 7 1 2 3 4
- 大小: 48.8 KB
分享到:
相关推荐
循环左移数组中的数据元素,使用循环队列实现。
请编写程序将一个大小为n的整数数组循环左移m位。如:1,2,3,4,5,6,7,8循环左移三位后结果是:4,5,6,7,8,1,2,3.
将一个n元一维向量向左旋转(即循环移位)i个位置。例如,当n=8,且i=3时,向量abcdefgh旋转为defghabc。能否使用数十个额外字节的存储空间,在正比于n的时间内完成?
设计一个代码将R中的序列循环左移P(0),即将R中的数据由 {X0,X1,……Xn-1}变换为{Xp,Xp+1,……,Xn-1,X0,X1,……,Xp-1} 分析:将前P个元素逆置,再将剩下的元素逆置,最后将所有元素逆置
本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a0a1⋯an−1)变换为(am⋯an−1...
编程珠玑上第二章问题A的实现,杂技法,3次反转法
给出数组和移位位数实现循环左移 一个子函数 头一次发哈
40-数码管循环左移(51单片机C语言实例Proteus仿真和代码)40-数码管循环左移(51单片机C语言实例Proteus仿真和代码)40-数码管循环左移(51单片机C语言实例Proteus仿真和代码)40-数码管循环左移(51单片机C语言实例...
数组的循环左移
reverse函数用于翻转指定区间内的元素。在left_rotate函数中,我们先将k取模以保证k小于n,然后分别对前k个数、剩下的n-k个数和整个数组进行翻转即可完成循环左移。
在主函数中输入10个整数到数组中,调用函数move()完成将数组元素循环移动k位(要求函数参数为:1数组名;2数组元素个数;3循环移动的位数k)。当k>0时,实现循环右移;当k时,实现循环左移。循环右移一位的意义是:将...
51单片机开发板实验:双灯左移右移闪烁程序源代码。 1、开发环境:KEIL。 2、编程语言:C语言。
内容:循环左移,始终一个led点亮,并循环执行流水动作,左移符号 逻辑或符号 |
数组结合指针可以实现很多有趣的功能,比如下面这个程序: 假设数组为 : 12345 如果左移一次即为:23451 ,...//数组左移 int buffer_left_move(int *buffer , int buf_len) { int i ; char tmp = buffer[0]; for
基于VC++的51单片机控制源码:利用循环左移函数流水灯
10-LED循环左移(51单片机C语言实例Proteus仿真和代码)10-LED循环左移(51单片机C语言实例Proteus仿真和代码)10-LED循环左移(51单片机C语言实例Proteus仿真和代码)10-LED循环左移(51单片机C语言实例Proteus仿真和代码)...
顺便bb:循环左移k位,等价于循环右移n-k位(n位字符串长度) 暴力法 思路:不是循环左移k位吗,那么就简单粗暴的一位一位的移动就是了。将首位暂存,后面的依次前移,最后将首位放到最后,就循环左移了1位,调用k次...