원형 배열에서 왼쪽 시프트를 어떻게 수행합니까?

Question

정수의 원형 배열에서 왼쪽 시프트를 수행하는 기존 방법이 있습니까?

특히 {1,2,3,4}의 4 개 항목과 시프트 양이 2 인 배열이 주어지면 첫 번째 두 글자를 배열의 뒤쪽으로 이동하여 다음과 같이 표시하는 방법을 원합니다. {3,4,1,2}.

이 알고리즘은 순환 배열을 하나씩 이동시킬 수 있습니까? 만약 n로 이동하고자한다고 가정

algShiftByOne(Array) 
{ 
    temp=array[0]; 
    i=1 
    while(i < Array.length - 1) // Loop from 1 up to array.length == last index 
    { 
    // If there is no exception i assume it copies value from 
    // initial array starting from 1 up to array.length 
    Array[i - 1] = Array[i]; 
    i++; 
    } 
Array[Array.length]=temp; 
} 

Answer 1

:

1. 복사 배열에서 첫 번째 N 개의 엘리먼트 이름, 예를 들면, 마지막에 n에서 각 요소 tempNumbers
2. 시프트 왼쪽에서 왼쪽으로 n
3. tempNumbers에서 원래 배열 끝까지 요소를 복사하십시오.

Answer 2

왜 원형 (중복) 연결 목록을 사용하지 않으십니까? 이 경우 '시작 포인터'만 변경하면됩니다.

Answer 3

다음은 원하는대로 의사 코드를 작성한 것입니다.

Array shift(Array a, int shiftLength) { 
    Array b; 

    for(i = shiftLength; i < a.size(); i++) 
     b.add(a.at(i)); 

    for(i = 0; i < shiftLength; i++) 
     b.add(a.at(i)); 

    return b; 
} 

Answer 4

이렇게하면 배열이 하나 왼쪽으로 이동합니다.

int[] a = new int[] { 1, 2, 3, 4, 5 }; 
int[] b = new int[a.length]; 
System.arraycopy(a, 1, b, 0, a.length - 1); 
b[a.length - 1] = a[0]; 
// b = {2,3,4,5,1} 
// edit 
a = b; 

Answer 5

여기 (여기 ideone.com demo입니다) ... 그것에 내 이동이다 나는 면접 질문 등이 하나 있었다

import java.util.Arrays; 

public class Test { 

    public static void circularShiftLeft(int[] arr) { 
     if (arr.length == 0) 
      return; 

     int first = arr[0]; 
     System.arraycopy(arr, 1, arr, 0, arr.length - 1); 
     arr[arr.length - 1] = first; 
    } 

    public static void main(String[] arg) { 
     int[] arr = { 1, 2, 3, 4 }; 
     System.out.println(Arrays.toString(arr)); 
     circularShiftLeft(arr); 
     System.out.println(Arrays.toString(arr)); 
    } 
} 

Answer 6

. m을 회전시키는 간단한 (그리고 다소 직관적 인) O (2n) 솔루션은 배열을 가져 와서 역순으로 한 다음 [0, m] 및 (m, n) 하위 배열을 뒤집을 수 있습니다. , in place and O (n)입니다. 기본적으로 아이디어는 항목을 하나의 항목에서 앞으로 회전시키고 결국 모든 요소를 ​​통과하게됩니다. 배열은 거리의 배수가되는 경우입니다. 즉, GCD . 온 다음은 오른쪽으로 회전을 할 것입니다, 왼쪽 연습으로 독자에게 남아 회전 :이 숙제

public static void main(String[] args) { 
    int[] f = {0, 4, 8, 2, 6, 7, 4, 5, 3}; 
    System.out.println(Arrays.toString(f)); 
    rotate(f, 3); 
    System.out.println(Arrays.toString(f)); 
} 

public static void rotate(int[] arr, int dist){ 
    int tmp, tmp2, gcd = GCD(arr.length, dist); 
    for(int off=0;off<gcd;off++){ 
     tmp = arr[off]; 
     for(int i=0,idx=off;i<arr.length/gcd;idx=(idx+dist)%arr.length,i++){ 
      tmp2 = arr[(idx+dist)%arr.length]; 
      arr[(idx+dist)%arr.length] = tmp; 
      tmp = tmp2; 
     } 
    } 
} 

public static int GCD(int a, int b) { 
    if (b==0) return a; 
    return GCD(b,a%b); 
} 

Answer 7

public static void shift(int[] arr, int offs) { 
    // e.g. arr = 1,2,3,4,5,6,7,8,9; offs = 3 
    offs %= arr.length; 
    offs = offs < 0 ? arr.length + offs : offs; 

    if (offs > 0) { 
     // reverse whole array (arr = 9,8,7,6,5,4,3,2,1) 
     for (int i = 0, j = arr.length - 1; i < j; i++, j--) 
      swap(arr, i, j); 
     // reverse left part (arr = 7,8,9,6,5,4,3,2,1) 
     for (int i = 0, j = offs - 1; i < j; i++, j--) 
      swap(arr, i, j); 
     // reverse right part (arr = 7,8,9,1,2,3,4,5,6) 
     for (int i = offs, j = arr.length - 1; i < j; i++, j--) 
      swap(arr, i, j); 
    } 
} 

private static void swap(int[] arr, int i, int j) { 
    int tmp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = tmp; 
}