C语言解读数组循环右移问题

目录

• C语言数组循环右移
• 函数接口定义
• 裁判测试程序样例
• 数组：如何把一个数组循环右移K位
• 问题描述
• 分析

C语言数组循环右移

本题要求实现一个对数组进行循环右移的简单函数：一个数组a中存有n（>0）个整数，将每个整数循环向右移m（≥0）个位置，即将a中的数据由(a₀,a₁,...,a_n−1)变为(a_n−m,...,a_n−1,a₀,a₁,...,a_n−m−1)即最后m个数循环移至最前面的m个位置）。

函数接口定义

int ArrayShift( int a编程客栈[], int n, int m );

其中a[]是用户传入的数组；n是数组的大小；m是右移的位数。函数ArrayShift须将循环右移后的数组仍然存在a[]中。

裁判测试程序样例

#include <stdio.h>
#define MAXN 10

int ArrayShift( int a[], int n, int m );

int main()
{
    in编程客栈t a[MAXN], n, m;
    int i;

    scanf("%d %d", &n, &m);
    for ( i = 0; i < n; i+开发者_C培训+ ) scanf("%d", &a[i]);

    ArrayShift(a, n, m);

    for ( i = 0; i < n; i++ ) {
        if (i != 0) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

6 2

1 2 3 4 5 6

输出样例：

5 6 1 2 3 4

解答：

int ArrayShift( int a[], int n, int m )
{
    if(m>=n) m-=n;        /*为了达到表内循环*/
    int b[100];
    for(int i=0;i<m;i++)
        b[i]=a[n-m+i];
    for(int i=0;i<n-m;i++)
        b[i+m]=a[i];
    for(int i=0;i<n;i++)
        a[i]=b[i];
}

数组：如何把一个数组循环右移K位

问题描述

假设要把数组12345678右移2位，变为78123456。

分析

方法一：

比较移位前后数组序列的形式，不难看出，其中有两段序列的顺序是不变的，即就是 78 和 123456， 可以把这两段看做两个整体，右移k位就是把数组的两部分交换一下。时间复杂度为O(n)

步骤：

1)逆序数组子序列123456，数组序列的形式为65432178

2)逆序数组子序列78， 数组序列的形式变为65432187

3)全部逆序， 数组序列的形式为78123456

代码：

private void shift_k1(int[] a, int k) {
  int n = a.length;
  k = k % n;
  reverse(a,0,n-k-1);
  reverse(a,n-k,n-1);
  reverse(a,0,n-1);
 }
private void reverse(int[] a, int i, int j) {
  for(; i<j; i++,j--){
   int t编程mp = a[i];
   a[i] = a[j];
   a[j] = tmp;
  }
 }

方法二：

使用arraylist来存储k位后面的数，数组的前K位依次向后移动k位，最后将集合中的后k位数放到a的前k位中，注意对于K需要%a.length.

代码：

private int[] shift_k(injst[] a, int k) {
  k = k % a.length;
  if(k == 0){
   return a;
  }
  ArrayList<Integer> q = new ArrayList<Integer>();
  for(int j=a.length-k; j<a.length; j++){
   q.add(a[j]);
  }
  for(int i=a.length-k-1;http://www.devze.com i>=0; i--){
   a[i+k] = a[i];
  }
  for(int i=0; i<k; i++){
   a[i] = q.get(i);
  }
  return a;
 }

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。