本题代码可以参考这里


原题: 1008. 数组元素循环右移问题 (20)

一个数组A中存有N(N>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(M>=0)个位置,即将A中的数据由(A0 A1……AN-1)变换为(AN-M …… AN-1 A0 A1……AN-M-1)(最后M个数循环移至最前面的M个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?

输入格式

每个输入包含一个测试用例,第1行输入N ( 1<=N<=100)、M(M>=0);第2行输入N个整数,之间用空格分隔。

输出格式

在一行中输出循环右移M位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。

输入样例1

6 2
1 2 3 4 5 6

输出样例1

5 6 1 2 3 4

注意

时间限制: 400 ms
内存限制: 65536 kB
代码长度限制: 8000 B
判题程序: Standard



题目分析

注意: 题目中右移位数可以大于总位数。即等效移动位数是

M = M % N;
  1. 方法1

    使用临时变量tmp,相邻交换,一次移动一位,移动M遍。

  2. 方法2

    变数据结构,使用循环队列,循环链表,空间换时间。其实也没有用太多空间,加了个指针而已。根据需要移动指针头,然后输出即可,数据本身不需要移动。

  3. 方法2简化

    借鉴链表的思想,改造数组,使其成为循环数组。

    • 数据结构

      typedef struct Node{
          int data;
          struct Node *next;
      }ListType;
      
    • 初始化

      ListType *init_list(ListType arr[], const int us_N){
          int i=0;
      
          for(i=0; i<us_N; i++){
              scanf("%d", &arr[i].data);
              arr[i].next = &arr[i+1];
          }
          arr[i-1].next = &arr[0];
      
          return &arr[0];
      }
      

      这种做法,在已知MAXSIZE时可以快速建立一个循环链表。可以移动头指针head。兼容链表的动态扩展。可以用数组的索引。

    • 移位

      左移 = M % us_N
      左移 + 右移 = us_N
      

      若用l_shift, r_shift分别代表左移和右移,则有

      ListType *shift_head(ListType *head, const int us_N, const int us_shift){
          int i=0, r_shift=0;
          // int l_shift=0;
      
          r_shift = us_N - us_shift%us_N;
          // l_shift = us_shift % us_N;
          for(i=0; i<r_shift; i++){
              head = head->next;
          }
      
          return head;
      }
      
    • 输出

      根据右移位数M,移动头指针,然后依次输出数据即可。注意行尾无空格。

      int print_list(ListType *head, const int us_N){
          int i=0, is_start=1;
      
          for(i=0; i<us_N; i++){
              if(is_start){
                  printf("%d", head->data);
                  is_start = 0;
              }else
                  printf(" %d", head->data);
              head = head->next;
          }
      
          return 0;
      }
      

部分测试用例

  • test1

    输入
    6 2
    1 2 3 4 5 6
    
    输出
    5 6 1 2 3 4
    

其他参考


(END)