C語言解讀數(shù)組循環(huán)右移問題
C語言數(shù)組循環(huán)右移
本題要求實(shí)現(xiàn)一個(gè)對數(shù)組進(jìn)行循環(huán)右移的簡單函數(shù):一個(gè)數(shù)組a中存有n(>0)個(gè)整數(shù),將每個(gè)整數(shù)循環(huán)向右移m(≥0)個(gè)位置,即將a中的數(shù)據(jù)由(a0,a1,...,an−1)變?yōu)?an−m,...,an−1,a0,a1,...,an−m−1)即最后m個(gè)數(shù)循環(huán)移至最前面的m個(gè)位置)。
函數(shù)接口定義
int ArrayShift( int a[], int n, int m );
其中a[]是用戶傳入的數(shù)組;n是數(shù)組的大小;m是右移的位數(shù)。函數(shù)ArrayShift須將循環(huán)右移后的數(shù)組仍然存在a[]中。
裁判測試程序樣例
#include <stdio.h> #define MAXN 10 int ArrayShift( int a[], int n, int m ); int main() { int a[MAXN], n, m; int i; scanf("%d %d", &n, &m); for ( i = 0; i < n; i++ ) 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; /*為了達(dá)到表內(nèi)循環(huá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]; }
數(shù)組:如何把一個(gè)數(shù)組循環(huán)右移K位
問題描述
假設(shè)要把數(shù)組12345678右移2位,變?yōu)?8123456。
分析
方法一:
比較移位前后數(shù)組序列的形式,不難看出,其中有兩段序列的順序是不變的,即就是 78 和 123456, 可以把這兩段看做兩個(gè)整體,右移k位就是把數(shù)組的兩部分交換一下。時(shí)間復(fù)雜度為O(n)
步驟:
1)逆序數(shù)組子序列123456,數(shù)組序列的形式為65432178
2)逆序數(shù)組子序列78, 數(shù)組序列的形式變?yōu)?5432187
3)全部逆序, 數(shù)組序列的形式為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 tmp = a[i]; ?? ??? ??? ?a[i] = a[j]; ?? ??? ??? ?a[j] = tmp; ?? ??? ?} ?? ?}
方法二:
使用arraylist來存儲k位后面的數(shù),數(shù)組的前K位依次向后移動k位,最后將集合中的后k位數(shù)放到a的前k位中,注意對于K需要%a.length.
代碼:
private int[] shift_k(int[] 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; i>=0; i--){ ?? ??? ??? ?a[i+k] = a[i]; ?? ??? ?} ?? ??? ?for(int i=0; i<k; i++){ ?? ??? ??? ?a[i] = q.get(i); ?? ??? ?} ?? ??? ?return a; ?? ?}
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
實(shí)現(xiàn)posix消息隊(duì)列示例分享
這篇文章主要介紹了實(shí)現(xiàn)posix消息隊(duì)列示例,學(xué)習(xí)記錄鎖,線程互斥量,線程條件變量,內(nèi)存映射,信號,線程的綜合應(yīng)用,需要的朋友可以參考下2014-02-02C++中為何推薦要把基類析構(gòu)函數(shù)設(shè)置成虛函數(shù)
這篇文章主要介紹了C++中為何推薦要把基類析構(gòu)函數(shù)設(shè)置成虛函數(shù)問題,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12vs2019創(chuàng)建WebService服務(wù)的實(shí)現(xiàn)
這篇文章主要介紹了vs2019創(chuàng)建WebService服務(wù)的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03C++實(shí)現(xiàn)關(guān)系與關(guān)系矩陣的代碼詳解
這篇文章主要介紹了C++實(shí)現(xiàn)關(guān)系與關(guān)系矩陣,功能實(shí)現(xiàn)包括關(guān)系的矩陣表示,關(guān)系的性質(zhì)判斷及關(guān)系的合成,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-04-04C++入門概覽和嘗試創(chuàng)建第一個(gè)C++程序
這篇文章主要介紹了C++入門概覽和嘗試創(chuàng)建第一個(gè)C++程序,同時(shí)也包括編寫類的示例展示C++面向?qū)ο蟮奶匦?需要的朋友可以參考下2015-09-09C++11 強(qiáng)類型枚舉相關(guān)總結(jié)
這篇文章主要介紹了C++11 強(qiáng)類型枚舉的相關(guān)資料,幫助大家更好的理解和學(xué)習(xí)使用c++11,感興趣的朋友可以了解下2021-02-02