当前位置:网站首页>Array cyclic shift problem
Array cyclic shift problem
2022-07-05 12:21:00 【A finger leaf next to the giant】
About array cyclic shift , stay Draw lessons from articles I learned three solutions in .
First, the first circular transposition algorithm , Not much .
Let's start with the second algorithm
Triple inversion algorithm :
The triple inversion algorithm completes the cyclic shift through triple inversion , For example, array [1,2,3,4,5], Then move three steps to the left , This can be done through the following functions :
reverse(0,2) ->[3,2,1,4,5]
reverse(2,4) ->[3,2,1,5,4]
reverse(0,4) ->[4,5,1,2,3]
If the number of steps is recorded as p, Array has n Number , Then there are :
reverse(0,p-1)
reverse(p,n-1)
reverse(0,n-1)
Indeed, before we look at the shift , The result after shift , You will find that the number of steps divides the array into two parts , Then the position of the two parts changed , The principle of position exchange achieved after three reversals can be understood in conjunction with the palm turning Algorithm :
Three reverses –> Palm turning algorithm :
At first, the palm was on our face , The left hand is on the right , First turn your left hand upside down ( Palm outward , Palm back to our face ), Turn your right hand over ( Same as left hand ), Finally, turn both hands at the same time , At this time, you will find , The palms of both hands are still facing us , But the stacking order of hands has changed .
// Using three inversions to realize cyclic shift
public class CircleGo_1 {
public static void reverse(int nums[],int a, int b) {
int middle;
// Note the reversal , It is the inversion from the first to the last number of the interval , The middle number does not change
for(int i=0;i<(b-a+1)/2;i++) {
middle=nums[a+i];
nums[a+i]=nums[b-i];
nums[b-i]=middle;
}
}
public static void main(String[] args) {
int nums[]= {
1,2,3,4,5};
int p =3,n=nums.length;
reverse( nums, 0,p-1);
reverse(nums, p,n-1);
reverse(nums,0,n-1);
System.out.println(Arrays.toString(nums));
}
}
Permutation loop algorithm :
In ordinary circular transposition algorithm , Need to move a few steps , It needs to be cycled several times , Move one step at a time , Such spatial complexity is O(1), The time complexity is O(nk). If k Less than n, be O(n^2).
that , Is it possible to directly move the number to be moved to the position after the cycle , such , Each number only needs to be moved once to complete the cyclic shift , So if possible , How to determine the specific location to move .
For example, the sequence subscript is [i] Number of numbers , Its cyclic shift k Step , Then it should be in [i+k] The location of ,[i+k] The number of positions should be [i+2k] The location of , Because each element moves to the right n After that, he returned to his original position , So move right k Bit equals shift right k mod n position . So there is such a sequence of positions :0,k,2k,…,(t-1)k. Each of them is in the mold n Position in the sense of .tk mod n The result is 0.t Is making tk mod n As the result of the 0 The smallest positive integer of . And t Is inevitable , The biggest is in t be equal to n When , In this way, a ring is formed .
To be exact, it forms a cyclic group .
This sequence of positions is essentially a module n The additive group consists of elements k Generate a cyclic subgroup . From the conclusion of group theory ( The proof of this conclusion is shown at the end ) know , Cyclic subgroup (k) The period of is n / gcd(k,n), The number of elements is n / gcd(k,n), The number of cosets is gcd(k,n). let me put it another way ,A[0…n-1] Cycle moves to the right k The result of bit is cyclic subgroup (k) And all its coset cycles are shifted one bit to the right . for example , take A[0…5] = {1,2,3,4,5,6} Cycle moves to the right 4 position , here n = 6, k = 4, gcd(k, n) = 2.A[0] The final position is 4,A[4] The final position is 2,A[2] The final position is 0, such , Location 0,4,2 It is from k=4 Generated cyclic group , The period is 6 / gcd(4,6) = 6 / 2 = 3, Such cyclic subgroups share gcd(4,6) = 2 individual .
So the complete code has , Make sure the gcd(k,n) Number of cyclic subgroups , Then shift the elements in the cyclic group one by one .
// Cyclic shift of array
#include <cstdio>
//gcd(x,y) Express x and y Maximum common factor of -- Euclidean algorithm
int gcd(int m, int n) {
int r;
//r Record the remainder , Divide the divisor by the remainder , Until the remainder is 0, At this point, the divisor is the greatest common factor
while (r = m % n) {
m = n;
n = r;
}
return n;
}
void shiftArray(int A[], int n, int k) {
// Because the code shifted to the left is much easier to implement than the code shifted to the right , And move right k position
// Equivalent to moving left -k position , Generally speaking, shift right k position , Equal to shift left n-k position . The following code is moved left n-k Bit to shift right k position
k = n - (k % n);
for (int i = 0, cnt = gcd(n, k); i < cnt; i++) {
int t = A[i], p = i, j = (k + i) % n;
while (j != i) {
A[p] = A[j]; p = j; j = (k + p) % n;
}
A[p] = t;
}
}
void printArray(int A[], int n) {
for (int i = 0; i < n; i++) {
printf("%-3d", A[i]);
}
}
int main() {
int A[] = {
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
printf(" Cycle to the right 12 Step \n");
shiftArray(A, 15, 12);
printArray(A, 15);
return 0;
}
边栏推荐
- Principle of redis cluster mode
- Complete activity switching according to sliding
- MySQL trigger
- Solution to order timeout unpaid
- abap查表程序
- Matlab imoverlay function (burn binary mask into two-dimensional image)
- Codeworks 5 questions per day (1700 average) - day 5
- Take you two minutes to quickly master the route and navigation of flutter
- Sentinel sentinel mechanism of master automatic election in redis master-slave
- MySQL transaction
猜你喜欢
ZABBIX customized monitoring disk IO performance
互联网公司实习岗位选择与简易版职业发展规划
Seven ways to achieve vertical centering
HiEngine:可媲美本地的云原生内存数据库引擎
Why learn harmonyos and how to get started quickly?
mysql拆分字符串做条件查询
Read and understand the rendering mechanism and principle of flutter's three trees
Matlab struct function (structure array)
Simply solve the problem that the node in the redis cluster cannot read data (error) moved
Hiengine: comparable to the local cloud native memory database engine
随机推荐
MySQL transaction
MySQL data table operation DDL & data type
强化学习-学习笔记3 | 策略学习
Uniapp + unicloud + Unipay realize wechat applet payment function
Use and install RkNN toolkit Lite2 on itop-3568 development board NPU
Take you two minutes to quickly master the route and navigation of flutter
MySQL installation, Windows version
Embedded software architecture design - message interaction
Just a coincidence? The mysterious technology of apple ios16 is actually the same as that of Chinese enterprises five years ago!
GPS数据格式转换[通俗易懂]
A guide to threaded and asynchronous UI development in the "quick start fluent Development Series tutorials"
Simply solve the problem that the node in the redis cluster cannot read data (error) moved
Time tools
About cache exceptions: solutions for cache avalanche, breakdown, and penetration
MySQL log module of InnoDB engine
嵌入式软件架构设计-消息交互
GPS數據格式轉換[通俗易懂]
Solution to order timeout unpaid
GPS data format conversion [easy to understand]
Intern position selection and simplified career development planning in Internet companies