精华内容
下载资源
问答
  • 数组循环左移问题

    2021-02-27 21:17:51
    数组循环左移问题的三种解法问题/题干 描述解法1解法2解法3 问题/题干 描述 将一个具有n个元素的数组向左循环移动i个位置。 这只一个很实用问题,很多应用程序会调用这个问题算法,例如在文本编辑器中移动行...

    数组循环左移问题的三种解法

    问题/题干 描述

    将一个具有n个元素的数组向左循环移动i个位置。
    这只一个很实用的问题,很多应用程序会调用这个问题的算法,例如在文本编辑器中移动行的操作,磁盘整理时交换两个不同大小的相邻内存块等。所有解决这个问题的算法要求有较高的时间性能和空间性能。

    解法1

    先将数组前i个元素存放于另一个临时数组,再将余下的n-i个元素左移i个位置,最后将前i个元素从临时数组复制会原数组后面i个位置。
    总共需要移动i+(n-i)+i=i+n次数组元素,使用了i个额外的存储单元。

    解法2

    设计一个函数,将数组向左循环1个位置,循环i次。
    移动i*n次数组元素,使用了1个额外数组单元。

    解法3

    换个角度看:
    把这个问题看做数组AB转换为数组BA的问题(A代表数组前i个元素,B代表余下n-i个元素)。
    先将A取逆得A-1B,再将B取逆得A-1B-1, 最后将整个A-1B-1取逆得BA
    下面通过reverse函数演示一下,对abcdefgh左移3个元素位置:
    reverse(0, i-1); cbadefgh
    reverse(i, n-1); cbahgfed
    reverse(0,n-1); defghabc

    该算法总共交换i/2 + (n-i)/2 + n/2 = n次数组元素,使用了1个用来交换的数组单元。
    Brian Kernighan 在Software Tools in Pascal中使用了这个算法在文本编辑器中移动各行。

    展开全文
  • 问题描述:对于给定的数组循环左移p个元素 说明:对于这个问题,我想了有三种方法。(当然,还参考了资料),把它们简要实现出 来了。现简要叙述如下: MoveLeft1:这种算法思路是,将第一个元素暂时...

    /*
    问题描述:对于给定的数组,循环左移p个元素
    说明:对于这个问题,我想了有三种方法。(当然,还参考了资料),把它们简要的实现出
    来了。现简要叙述如下:
    MoveLeft1:这种算法的思路是,将第一个元素暂时保存在temp,然后把后面要移动到这个位置的元素放在这个位置,接着再把这个元素后面的元素移动到第二个位置。就这样,一步一步直到最后一个元素。要有一点说明的是,这种算法需要保存一个指针,保存的是正在左移的组是哪一组,为的是有些情况是重复移动的。比如说:1,3,2,5,4,6(移动两个元素)。
    说的有点复杂,直接看图:

    这里写图片描述

    这个算法的时间复杂是O(N),空间复杂度是O(1)

    MoveLeft2:第二种方法是我参考王道资料上的。人家想的思路就是比我的要清晰。1,3,2,5,4,6(移动两个元素)。最终的结果是2,5,4,6,1,3。
    (1)、我先逆转前两个元素:(3,1,2,5,4,6)。
    (2)、再逆转后面的四个元素:(3,1,6,4,5,2)
    (3)、再把整个数组逆转一下。即得到(2,5,4,6,1,3)。
    牛逼的思路。和我之前说的一种思路差不多,就是以结果推过程。
    这种算法的时间复杂度是O(N),空间复杂度为O(1)

    MoveLeft3:这个算法的思路最简单。就是把前p个元素先转移出来,然后移动后面的元素。最后再把转移的元素放在后面。
    这种算法的时间复杂度是O(N),空间复杂度取决于p即左移的元素个数。

    */

    //循环左移1
    void MoveLeft1(Sqlist &L,int p)
    {
        int temp_index = 0,temp_val = L.data[0];    //首先保存第一个元素和下标
    
        int move_cou = 0;   //用来保存已经移动的元素的个数
        int i = 0,j = 0;
        while(move_cou < L.length)
        {
            j = (i+p) % L.length;   //要移动到此位置的元素的位置
            if(j == temp_index )    //如果和标志指针相同,说明构成了一个循环组,下一次需要从下一组开始
            {
                L.data[i] = temp_val;
                ++temp_index;
                temp_val = L.data[temp_index];
                i = temp_index;
            }
            else
            {
                L.data[i] = L.data[j];
                i = j;
            }
    
            ++move_cou;
        }
    
    }
    //逆转元素
    void Reverse(Sqlist &L,int st,int _end)
    {
        int temp;
        while(st<_end)
        {
            temp = L.data[st];
            L.data[st] = L.data[_end];
            L.data[_end] = temp;
    
            ++st;
            --_end;
        }
    }
    
    //循环左移2
    void MoveLeft2(Sqlist &L,int p)
    {
        p = p%L.length;
        Reverse(L,0,p-1);
        Reverse(L,p,L.length-1);
        Reverse(L,0,L.length-1);
    
    }
    
    
    //循环左移3
    void MoveLeft3(Sqlist &L,int p)
    {
         p = p%L.length;
        //将前p的元素暂时保存在temp数组中
        int temp[p];
        for(int i = 0;i<p;++i)
        {
            temp[i] = L.data[i];
        }
    
        int j = 0;
        for(int i = 0;i<L.length;++i)
        {
            if(i<L.length-p)        //移动后面L.leng-p个元素
                L.data[i] = L.data[i+p];
    
            else                        //将temp中的元素放在原数组后面
                L.data[i] = temp[j++];
    
        }
    
    }
    展开全文
  • 问题描述:把一个数组元素循环右移k位,时间复杂度严格为O(n),不能是O(kn).分析:对于这个问题很容易想到一种方法是依次循环右移,但是这样话时间复杂度是O(kn),明显不符合题目要求,在之前博客中,我写...

    问题描述:把一个数组中的元素循环右移k位,时间复杂度严格为O(n),不能是O(kn).

    分析:对于这个问题很容易想到的一种方法是依次循环右移,但是这样的话时间复杂度是O(kn),明显不符合题目要求,在之前的博客中,我写的对于字符串的移位问题,可以借助里面的方法三步反转法。

    第一步:根据n和k求出分界点的下标,假设为index,则index=n-k(数组下标从0开始),将整个数组分为两部分,0~index-1和index~n-1,

    第二步:将0~index-1部分反转。

    第三布:将index~n-1部分反转。

    第四步:将整个数组反转。

    具体的Java实现代码如下:

    public class Main {

    public static void removerightk(int a[],int k){

    if(k<0)return; //如果k小于0,则退出

    k=k%a.length; //由于k可能大于n,所以将k化为1~n之间

    int index=a.length-k;

    reverse(a,0,index-1);

    reverse(a,index,a.length-1);

    reverse(a,0,a.length-1);

    }

    public static void reverse(int a[],int s,int e){

    while(s

    int t=a[s];

    a[s]=a[e];

    a[e]=t;

    s++;

    e--;

    }

    }

    public static void main(String[] args) {

    int a[]={0,1,2,3,4,5,6,7,8,9};

    removerightk(a, 2);

    for(int i=0;i

    System.out.print(a[i]+",");

    }

    }

    展开全文
  • 设计一个时间复杂度为 O(n)O(n)O(n) 算法,实现将数组 A[n] 中所有元素循环左移 kkk 个位置。 详见王红梅等编著《数据结构(C++版)(第2版)》P53页习题5(1)。 二、基本要求 实现将数组 A[n] 中所有元素循环...

    课程设计题目:用 Reverse 实现时间复杂度为 O(n)O(n) 数组循环左移算法

    一、问题描述

    设计一个时间复杂度为 O(n)O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 kk 个位置。

    详见王红梅等编著的《数据结构(C++版)(第2版)》P53页习题5(1)。

    二、基本要求

    1. 实现将数组 A[n] 中所有元素循环左移 kk 个位置。

    2. 时间复杂度为 O(n)O(n)

    三、概要设计

    1. 算法的设计

    算法思路参考王红梅等编著的《数据结构(C++版)(第2版)》P16页思想火花,出自BW Kernighan和PJ Plauger于1981年发表的著作Software tools in Pascal

    1. 设计reverse(first, last)函数,用于实现反转从firstlast(不含)之间的元素;

    2. 通过3次reverse实现将数组 A[n] 中所有元素循环左移 kk 个位置:

      reverse(a, a + k)

      reverse(a + k, a + n)

      reverse(a, a + n)

    四、详细设计

    1. 设计每个函数

    void Reverse(int *first, int *last)
    {
        last--;
        for (int temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    

    2. 设计主函数

    int main()
    {
        reverse(a, a + k);
        reverse(a + k, a + n);
        reverse(a, a + n);
    }
    

    五、运行与测试

    1. 测试环境

    运行环境:Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

    编译器:gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

    编译命令:-g

    运行终端:cmd

    2. 在调试程序的过程中遇到的问题与解决方案

    暂未发现异常。

    3. 设计的测试数据与测试结果

    测试3次。输入k,然后生成一个随机数组并输出,数组所有元素循环左移 kk 个位置后再输出。

    4. 程序清单及运行结果

    4.1 A[n] 为整型数组

    程序清单如下。

    // ex1_2.cpp
    
    /*
     * 1. 编写程序:课本p53页习题5(1),先做整数,然后改用模板函数做并测试。
     * 课本p53页习题5(1):设计一个时间复杂度为 O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 k 个位置。
     * 模板
     */
    
    #include <iostream>
    #include <ctime>
    using namespace std;
    
    template <typename T>
    void Reverse(T *first, T *last)
    {
        last--;
        for (T temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    
    int main()
    {
        srand(time(NULL));
    
        int n = 10, k;
        cout << "Please input k(0 < k < 10): ";
        cin >> k;
    
        int A[n];
        for (int i = 0; i < n; i++)
            cout << (A[i] = rand()) << " ";
        cout << endl;
    
        Reverse(A, A + k);
        Reverse(A + k, A + n);
        Reverse(A, A + n);
    
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    
        double B[n];
        for (int i = 0; i < n; i++)
            cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
        cout << endl;
    
        Reverse(B, B + k);
        Reverse(B + k, B + n);
        Reverse(B, B + n);
    
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
        cout << endl;
    
        return 0;
    }
    

    第1次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 3
    31255 22925 30731 23452 21176 11048 16126 26806 17875 16867
    23452 21176 11048 16126 26806 17875 16867 31255 22925 30731

    第2次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 4
    31297 31583 821 8595 24193 29328 23820 21519 3149 2478
    24193 29328 23820 21519 3149 2478 31297 31583 821 8595

    第3次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 5
    31310 9040 6742 6545 32684 12267 3502 9810 3660 10654
    12267 3502 9810 3660 10654 31310 9040 6742 6545 32684

    4.2 模板

    #include <iostream>
    #include <ctime>
    using namespace std;
    
    template <typename T>
    void Reverse(T *first, T *last)
    {
        last--;
        for (T temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    
    int main()
    {
        srand(time(NULL));
    
        int n = 10, k;
        cout << "Please input k(0 < k < 10): ";
        cin >> k;
    
        int A[n];
        for (int i = 0; i < n; i++)
            cout << (A[i] = rand()) << " ";
        cout << endl;
    
        Reverse(A, A + k);
        Reverse(A + k, A + n);
        Reverse(A, A + n);
    
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    
        double B[n];
        for (int i = 0; i < n; i++)
            cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
        cout << endl;
    
        Reverse(B, B + k);
        Reverse(B + k, B + n);
        Reverse(B, B + n);
    
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
        cout << endl;
    
        return 0;
    }
    

    第1次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 3
    31607 4105 26750 850 21038 9151 24591 5572 31655 8236
    850 21038 9151 24591 5572 31655 8236 31607 4105 26750
    0.551057 2.53344 0.209033 6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277
    6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277 0.551057 2.53344 0.209033

    第2次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 4
    31624 25079 17767 22863 7075 28785 7385 23704 15909 10263
    7075 28785 7385 23704 15909 10263 31624 25079 17767 22863
    0.511611 0.172095 1.52812 1.01504 0.720147 9.04 10.3216 0.00956241 2.05172 0.394671
    0.720147 9.04 10.3216 0.00956241 2.05172 0.394671 0.511611 0.172095 1.52812 1.01504

    第3次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 5
    31653 23511 14704 10057 1602 31357 2629 30126 673 20467
    31357 2629 30126 673 20467 31653 23511 14704 10057 1602
    0.4426 0.60074 5.66135 0.316398 0.906047 2.21183 135.865 0.0243682 0.37898 0.211203
    2.21183 135.865 0.0243682 0.37898 0.211203 0.4426 0.60074 5.66135 0.316398 0.906047

    六、总结与心得

    算法之美,妙不可言!

    七、参考资料

    1. 王红梅, 胡明, 王涛. 数据结构 (C++ 版)[M]. 清华大学出版社, 2005.

    2. Kernighan B W, Plauger P J. Software tools in Pascal[J]. 1981.

    展开全文
  • 问题描述:数组元素循环左移,将包含 num_elem 个元素的一维数组 arr[num_elem] 循环左移 rot_dist 位。能否仅使用数十个额外字节的存储空间,在正比于num_elem的时间内完成数组的旋转? 一:Bentley's Juggling ...
  • 对于一个任意长度为len的数组A,使其循环左移P个元素。如数组{1,2,3,4,5,6,7},左移3个元素即变为{4,5,6,7,1,2,3}。 实现算法 方法一 对前3个元素完全转置,变为{3,2,1,4,5,6,7} 对后4个元素完全转置,变为{3,2...
  • 对于一个任意长度为len的数组A,使其循环左移P个元素。如数组{1,2,3,4,5,6,7},左移3个元素即变为{4,5,6,7,1,2,3}。 实现算法 方法一 对前3个元素完全转置,变为{3,2,1,4,5,6,7} 对后4个元素完全转置,变为{3,2,1,7,6...
  • 1)个整数存放到一维数组arr中,设计一个在时间和空间两方面都尽可能高效算法,将arr中保存序列循环左移p(0<p<n)个位置,即将arr中数据由(X0,X1,...,Xn-1)变换为(Xp,Xp+1,...,Xn-1,X0,X1,...,Xp-1)。 ...
  • 问题描述】设将n(n>1)个整数存放在一维数组R中。试设计一个在时间和空间两方面都尽可能高效算法。将R中保存序列循环左移P(P>0)个位置。 例如,假设P<n,将R中数据(X0,X1……Xn-1)循环左移P个...
  • 将R中保存序列循环左移p(0<p<n)个位置,即将R中数据(x0,x1,x2,...x(n-1))变换为(xp,x(p+1),...,x(n-1),x0,x1,...,x(p-1))。 算法设计思想:可以将线性表中前p个元素当成一个数组,第p+1到第n个元素当成...
  • 不要犯笔者错误,笔者一开始理解错了题意,想成了左移,已注释,也粘贴了上来 #include <iostream> #include <bits/stdc++.h> using namespace std; int A[1000000000]; //下为左移 /*int main(int ...
  • 数组循环移位

    2014-03-07 08:50:14
    有一个长度为m的数组a,循环左移或右移n为 算法 三次逆置法 1 若循环左移,则将左边长度为n数组和右边剩下数组分别逆置 2 若循环右移,则将右边长度为n数组和左边剩下数组分别逆置 3 再将整个数组...
  • 问题 H: 循环左移

    2017-08-05 09:20:29
    题目描述 对于数组 (a0,a1,...,an−1),循环左移 k 位意味着将数组变为 (ak,ak+1,...,an−1,a0,a1,...,ak−1)。...输入第一行输入两个整数 n(1≤n≤100) 和 k(0≤k≤n),分别表示数组的元素个数和循环左移的位移量。
  • 即将字符串的循环左移k位 顺便bb:循环左移k位,等价于循环右移n-k位(n位字符串长度) 暴力法 思路:不是循环左移k位吗,那么就简单粗暴的一位一位的移动就是了。将首位暂存,后面的依次前移,最后将首位放到最后,...
  • 数组循环p个位置

    2020-03-28 22:10:47
    试设计一个在时间和空间两方面都尽可能高效算法,将R中保存序列循环左移p (0<p<n) 个位置,即将R中数据序列由(x0, x1,……,xn-1)变换为(xp,xp+1,……,xn-1,x0,x1,……,xp-1)。 2、算法基本...
  • 设计一个算法,把一个含有N元素的数组循环左移或者右移K位。 解决方法: 1. 暴力解法------O(KN) 2. 颠倒位置------O(N) 具体思路和代码: 1. 暴力解法------O(KN) 思路:循环K次,每次移动一位 代码: ...
  • 问题描述 分析与解法  假如数组为abcd1234,循环右移4位话,我们希望到达状态是1234abcd。不妨设K是一个非负整数,当K为负整数时候,右移K位,想当于左移(-K)位。左移和右移在本质上是一样。 ...
  • 1)个整数存放到一维数组R中,设计一个算法,将R中序列循环左移P (0<P<n) 个位置,即将R中数据由{Xo,X, …, Xn-1}变换为{Xp,Xp+1, … Xn-1, X0,X1, …,Xp-1}。要求写出本题算法描述。 二、【问题...
  • 蛇型矩阵-二维数组

    2019-03-01 22:21:41
    问题描述:在矩阵中心从1开始以逆时针方向绕行,逐圈扩大,直到n行n列填满数字 并输出矩阵对角线数字之和。 输入样例: 3 输出样例: 5 4 3 6 1 2 7 8 9 25 解题思路: 定义四个方向,比如我们用k来代替方向,k为0...
  • 问题描述】输入10个整数(存入数组a),再输入整数x;要求编写函数实现将该数组元素向左移x个位置后循环输出。要求在主函数中输入a数组,并输出最后结果,在被调函数中实现循环左移x个位置。 【输入形式】输入10...
  • 字符串的循环移位

    2012-08-16 10:38:57
    问题描述: ... 直接将前i个数组复制到一个临时数组,将余下元素左移,再将临时数组i个元素复制到末尾方法可得正确解,但空间复杂度为O(n)。每次移动一个到末尾,剩余前移也能得...
  • 问题描述: ... 直接将前i个数组复制到一个临时数组,将余下元素左移,再将临时数组i个元素复制到末尾方法可得正确解,但空间复杂度为O(n)。每次移动一个到末尾,剩余前移也能得正确解
  • 问题描述: 要求在时间复杂度和空间复杂度分别为O(n)和O(1)条件下把一个长度为N字符串循环左移M位,例如将长度为9字符串"123456789"循环左移4位后得到字符串"567891234"。程序输入为N(字符串长度)和M(循环...
  • 问题描述:一个数组a进行做循环移动k次,然后输出a。  example  input:1 2 3 4 5 6 ,左移3位 output:4 5 6 1 2 3. #include #include #include #include void leftmove1(int *a, int len, int k); void ...
  • C++队列排序问题

    2020-12-19 23:40:09
    本关要求编写函数rotateLeft,该函数实现对一个 n × n 方阵中每个元素循环左移 m 个位置( 0 < m < n ),即将第 0 、 1 、…、 n - 1 列变换为第 n - m 、 n - m + 1 、…、 n - 1 、 0 、 1 、…、 n -...
  • 左旋转字符串

    2019-08-06 21:20:00
    汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单任务,就是用字符串模拟这个指令运算结果。对于一个给定字符序列S,请你把其循环左移K位后序列输出。例如,字符序列S=”abcXYZdef”,要求输出...
  • 1、问题描述: 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单任务,就是用字符串模拟这个指令运算结果。对于一个给定字符序列S,请你把其循环左移K位后序列输出。例如,字符序列S=”abcXYZdef...
  • 字符串字符串主要内容字符串的循环左移问题分析优雅一点的算法CodeLCS的定义LCS的意义暴力求解:穷举法LCS的记号LCS解法的探索举例LCS的探索举例LCS分析总结算法中的数据结构:长度数组算法中的数据结构:方向变量...

空空如也

空空如也

1 2 3
收藏数 46
精华内容 18
关键字:

数组的循环左移问题描述