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