題目:一個(gè)數(shù)組A中存有 n 個(gè)整數(shù),在不允許使用另外數(shù)組的前提下,將每個(gè)整數(shù)循環(huán)向右移 M( M >=0)個(gè)位置,即將A中的數(shù)據(jù)由(A0 A1 ……AN-1 )變換為(AN-M …… AN-1 A0 A1 ……AN-M-1 )(最后 M 個(gè)數(shù)循環(huán)移至最前面的 M 個(gè)位置)。如果需要考慮程序移動(dòng)數(shù)據(jù)的次數(shù)盡量少,要如何設(shè)計(jì)移動(dòng)的方法?
題目分析:比如一個(gè)數(shù)組int[]={1,2,3,4,5,6};將數(shù)組右移2(m位)位1的位置移到3,2的位置移到4,3的位置移到5,4的位置移到6,如果5和6向后移,會(huì)數(shù)組越界,所以將5放到1的位置,6放到2的位置。要的結(jié)果是{5,6,1,2,3,4}想要達(dá)到這種效果1、首先我們可以將整個(gè)數(shù)組翻轉(zhuǎn)為{6,5,4,3,2,1}2、根據(jù)位移的數(shù),判斷前半段和后半段,位移的數(shù)為2位前半段起始終止位為(0,m-1)將前半段翻轉(zhuǎn)為{5,6}3、以此類(lèi)推,將后半段翻轉(zhuǎn)為(1,2,3,4)最后返回{5,6,1,2,3,4}要完成以上翻轉(zhuǎn),首先,我們需要?jiǎng)?chuàng)造一個(gè)翻轉(zhuǎn)函數(shù)當(dāng)起始點(diǎn)小于終止點(diǎn)時(shí),循環(huán)替換起始和終止的位置,每循環(huán)一次,起始點(diǎn)增加,終止點(diǎn)減小。具體鍵代碼。
import java.util.*;public class Solution { /** * 旋轉(zhuǎn)數(shù)組 * @param n int整型 數(shù)組長(zhǎng)度 * @param m int整型 右移距離 * @param a int整型一維數(shù)組 給定數(shù)組 * @return int整型一維數(shù)組 */ public int[] solve (int n, int m, int[] a) { //當(dāng)m的值大于n時(shí),取余是為了使m最小化 m = m%n; //將數(shù)組所有翻轉(zhuǎn)一遍 reverse(a,0,n - 1); //將數(shù)組前半部分翻轉(zhuǎn) reverse(a,0,m - 1); //將數(shù)組后半部分翻轉(zhuǎn) reverse(a, m, n - 1); return a; } //定義一個(gè)翻轉(zhuǎn)函數(shù) public void reverse(int[] a,int start,int end){ //當(dāng)起始下標(biāo)小于終點(diǎn)下標(biāo)時(shí),替換兩個(gè)下標(biāo)的內(nèi)容 while(start
輸入:6,2,[1,2,3,4,5,6]輸出:[5,6,1,2,3,4]