M 위치에 대한 N 크기 배열의 원 이동을 위한 가장 빠른 알고리즘

Question

M 위치에 대한 원 이동 배열의 가장 빠른 알고리즘은 무엇입니까?
예를 들어, [3 4 5 2 3 1 4] Shift M = 2 위치가 되어야 합니다. [1 4 3 4 5 2 3].

정말 감사합니다.

Answer 1

O(n) 시간을 원하고 추가 메모리 사용을 원하지 않는 경우(배열이 지정되었으므로) Jon Bentley의 저서 "Programming Pearls 2nd Edition"에 있는 알고리즘을 사용하십시오.모든 요소를 ​​두 번 교체합니다.연결된 목록을 사용하는 것만큼 빠르지는 않지만 메모리를 덜 사용하고 개념적으로 간단합니다.

shiftArray( theArray, M ):
    size = len( theArray )
    assert( size > M )
    reverseArray( theArray, 0, size - 1 )
    reverseArray( theArray, 0, M - 1 )
    reverseArray( theArray, M, size - 1 )

reverseArray( anArray, startIndex, endIndex ) 는 startIndex부터 endIndex(포함)까지 요소 순서를 반대로 바꿉니다.

Answer 2

그것은 단지 표현의 문제 일뿐입니다. 현재 색인을 정수 변수로 유지하고 배열을 가로 질러 모듈로 연산자를 사용하여 언제 랩을 해야하는지 알아보십시오. 그런 다음 이동은 현재 인덱스의 값 만 변경하여 배열의 크기 주위에 래핑합니다. 이것은 물론 o (1)입니다.

예를 들어:

int index = 0;
Array a = new Array[SIZE];

get_next_element() {
    index = (index + 1) % SIZE; 
    return a[index];
}

shift(int how_many) {
    index = (index+how_many) % SIZE;
}

Answer 3

최적의 솔루션

질문이 가장 빠르게 요청되었습니다.세 번 뒤집는 것이 가장 간단하지만 모든 요소를 ​​정확히 두 번 이동하므로 O(N) 시간과 O(1) 공간이 필요합니다.O(N) 시간과 O(1) 공간에서도 각 요소를 정확히 한 번 이동하는 배열을 원 이동하는 것이 가능합니다.

아이디어

길이의 배열을 순환 이동시킬 수 있습니다 N=9 ~에 의해 M=1 한 주기로:

tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;

그리고 만약에 N=9, M=3 우리는 세 가지 주기로 순환 이동을 할 수 있습니다:

1. tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
2. tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
3. tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;

각 요소는 한 번 읽고 한 번 작성됩니다.

변화의 다이어그램 N=9, M=3

첫 번째 사이클은 작업 순서를 나타내는 숫자와 함께 검은색으로 표시됩니다.두 번째 및 세 번째 사이클은 회색으로 표시됩니다.

필요한 사이클 수는 최대 공약수 (GCD)의 N 그리고 M.GCD가 3이면 각 지점에서 사이클을 시작합니다. {0,1,2}.GCD 계산은 다음과 같이 빠릅니다. 이진 GCD 알고리즘.

예제 코드:

// n is length(arr)
// shift is how many place to cycle shift left
void cycle_shift_left(int arr[], int n, int shift) {
  int i, j, k, tmp;
  if(n <= 1 || shift == 0) return;
  shift = shift % n; // make sure shift isn't >n
  int gcd = calc_GCD(n, shift);

  for(i = 0; i < gcd; i++) {
    // start cycle at i
    tmp = arr[i];
    for(j = i; 1; j = k) {
      k = j+shift;
      if(k >= n) k -= n; // wrap around if we go outside array
      if(k == i) break; // end of cycle
      arr[j] = arr[k];
    }
    arr[j] = tmp;
  }
}

모든 배열 유형에 대해 C로 코드를 작성합니다.

// circle shift an array left (towards index zero)
// - ptr    array to shift
// - n      number of elements
// - es     size of elements in bytes
// - shift  number of places to shift left
void array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift)
{
  char *ptr = (char*)_ptr;
  if(n <= 1 || !shift) return; // cannot mod by zero
  shift = shift % n; // shift cannot be greater than n

  // Using GCD
  size_t i, j, k, gcd = calc_GCD(n, shift);
  char tmp[es];

  // i is initial starting position
  // Copy from k -> j, stop if k == i, since arr[i] already overwritten
  for(i = 0; i < gcd; i++) {
    memcpy(tmp, ptr+es*i, es); // tmp = arr[i]
    for(j = i; 1; j = k) {
      k = j+shift;
      if(k >= n) k -= n;
      if(k == i) break;
      memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k];
    }
    memcpy(ptr+es*j, tmp, es); // arr[j] = tmp;
  }
}

// cycle right shifts away from zero
void array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift)
{
  if(!n || !shift) return; // cannot mod by zero
  shift = shift % n; // shift cannot be greater than n
  // cycle right by `s` is equivalent to cycle left by `n - s`
  array_cycle_left(_ptr, n, es, n - shift);
}

// Get Greatest Common Divisor using binary GCD algorithm
// http://en.wikipedia.org/wiki/Binary_GCD_algorithm
unsigned int calc_GCD(unsigned int a, unsigned int b)
{
  unsigned int shift, tmp;

  if(a == 0) return b;
  if(b == 0) return a;

  // Find power of two divisor
  for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; }

  // Remove remaining factors of two from a - they are not common
  while((a & 1) == 0) a >>= 1;

  do
  {
    // Remove remaining factors of two from b - they are not common
    while((b & 1) == 0) b >>= 1;

    if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b
    b = b - a;
  }
  while(b != 0);

  return a << shift;
}

편집하다:이 알고리즘은 배열 반전에 비해 더 나은 성능을 가질 수도 있습니다( N 크고 M 작음) 캐시 지역성으로 인해 작은 단계로 배열을 반복하기 때문입니다.

최종 참고사항: 배열이 작으면 삼중 역방향이 간단합니다.큰 배열이 있는 경우 GCD를 계산하여 이동 횟수를 2배로 줄이는 오버헤드는 가치가 있습니다.참조: http://www.geeksforgeeks.org/array-rotation/

Answer 4

포인터로 설정하면 거의 시간이 걸리지 않습니다. 각 요소는 다음 요소를 가리키고 "마지막"(마지막은 없으며 결국 원형이라고 말했습니다)은 첫 번째 요소를 포인트합니다. "시작"(첫 번째 요소)에 대한 하나의 포인터와 길이가있을 수 있으며 배열이 있습니다. 이제 교대를하기 위해 원을 따라 시작 포인터를 걷습니다.

좋은 알고리즘을 요청하면 현명한 아이디어를 얻습니다. 요청하십시오 가장 빠른, 그리고 당신은 이상한 아이디어를 얻습니다!

Answer 5

이 알고리즘은 O (N) 시간 및 O (1) 공간으로 실행됩니다. 아이디어는 교대에서 각 순환 그룹을 추적하는 것입니다 (번호 번호 nextGroup 변하기 쉬운).

var shiftLeft = function(list, m) {
    var from = 0;
    var val = list[from];
    var nextGroup = 1;
    for(var i = 0; i < list.length; i++) {
        var to = ((from - m) + list.length) % list.length;
        if(to == from)
            break;

        var temp = list[to];
        list[to] = val;
        from = to;
        val = temp;

        if(from < nextGroup) {
            from = nextGroup++;
            val = list[from];
        }
    }
    return list;
}

Answer 6

def shift(nelements, k):       
    result = []
    length = len(nelements)
    start = (length - k) % length
    for i in range(length):
        result.append(nelements[(start + i) % length])
    return result

이 코드는 Negative Shift k에서도 잘 작동합니다

Answer 7

C ArraysHifTright 함수. Shift가 음수 인 경우 함수는 배열을 왼쪽으로 이동시킵니다. 메모리 사용량이 줄어들면서 최적화됩니다. 실행 시간은 O (N)입니다.

void arrayShiftRight(int array[], int size, int shift) {
    int len;

    //cut extra shift
    shift %= size;

    //if shift is less then 0 - redirect shifting left
    if ( shift < 0 ) {
        shift += size;
    }

    len = size - shift;

    //choosing the algorithm which needs less memory
    if ( shift < len ) {
        //creating temporary array
        int tmpArray[shift];

        //filling tmp array
        for ( int i = 0, j = len; i < shift; i++, j++ ) {
            tmpArray[i] = array[j];
        }

        //shifting array
        for ( int i = size - 1, j = i - shift; j >= 0; i--, j-- ) {
            array[i] = array[j];
        }

        //inserting lost values from tmp array
        for ( int i = 0; i < shift; i++ ) {
            array[i] = tmpArray[i];
        }
    } else {
        //creating temporary array
        int tmpArray[len];

        //filling tmp array
        for ( int i = 0; i < len; i++ ) {
            tmpArray[i] = array[i];
        }

        //shifting array
        for ( int i = 0, j = len; j < size; i++, j++ ) {
            array[i] = array[j];
        }

        //inserting lost values from tmp array
        for ( int i = shift, j = 0; i < size; i++, j++ ) {
            array[i] = tmpArray[j];
        }
    }
}

Answer 8

매우 간단한 솔루션. 이것은 매우 빠른 방법입니다. 여기서는 크기가 같은 템프 배열을 사용하고 끝에 원래 변수에 연결됩니다. 이 방법은 O (n) 시간적 복잡성 및 O (N) 공간 복잡성을 사용하며 구현하기가 매우 간단합니다.

int[] a  = {1,2,3,4,5,6};
    int k = 2;
    int[] queries = {2,3};

    int[] temp = new int[a.length];
    for (int i = 0; i<a.length; i++)
        temp[(i+k)%a.length] = a[i];

    a = temp;

Answer 9

사용하는 데이터 구조에 따라 O (1)에서 수행 할 수 있습니다. 가장 빠른 방법은 링크 된 목록의 형태로 배열을 고정하고 배열의 "색인"사이에서 "포인터"로 항목으로 번역 할 수있는 해시 테이블을 갖는 것입니다. 이렇게하면 O (1)에서 관련 헤드와 테일을 찾아서 O (1)에서 재 연결을 수행 할 수 있습니다 (O (1)의 스위치 후 해시 테이블을 업데이트). 물론 이것은 매우 "지저분한"솔루션이지만, 관심이있는 모든 것이 교대의 속도라면 (배열에서 더 긴 삽입 및 조회를 희생 시키면서도 여전히 O)됩니다. 1))

순수한 배열에 데이터가 있다면 O (n)을 피할 수 없다고 생각합니다.

코딩 측면에서 사용하는 언어에 따라 다릅니다.

예를 들어 Python에서는 "슬라이스"할 수 있습니다 (N이 시프트 크기라고 가정) :

result = original[-n:]+original[:-n]

(해시 조회가 이론적으로 O가 아니라는 것을 알고 있습니다 (1) 우리는 여기서 실용적이지 않고 이론적이지 않습니다. 적어도 그렇게 희망합니다 ...)

Answer 10

이것은 Arry를 원형으로 변속하기 위해 작동해야합니다. 입력 : {1, 2, 3, 5, 6, 7, 8}; Forloops 다음 배열에 존재하는 출력 값 : {8,7,1,2,3,5,8,7}

 class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 1, 2, 3, 5, 6, 7, 8 };
            int index = 2;
            int[] tempArray = new int[array.Length];
            array.CopyTo(tempArray, 0);

            for (int i = 0; i < array.Length - index; i++)
            {
                array[index + i] = tempArray[i];
            }

            for (int i = 0; i < index; i++)
            {
                array[i] = tempArray[array.Length -1 - i];
            }            
        }
    }

Answer 11

다음은 C ++의 단순하고 효율적인 일반 회전 기능이 10 줄 미만입니다.

다른 질문에 대한 내 대답에서 발췌 한 것입니다. 배열을 회전시키는 방법?

#include <iostream>
#include <vector>

// same logic with STL implementation, but simpler, since no return value needed.
template <typename Iterator>
void rotate_by_gcd_like_swap(Iterator first, Iterator mid, Iterator last) {
    if (first == mid) return;
    Iterator old = mid;
    for (; mid != last;) {
        std::iter_swap(first, mid);
        ++first, ++mid;
        if (first == old) old = mid; // left half exhausted
        else if (mid == last) mid = old;
    }
}

int main() {
    using std::cout;
    std::vector<int> v {0,1,2,3,4,5,6,7,8,9};
    cout << "before rotate: ";
    for (auto x: v) cout << x << ' '; cout << '\n';
    int k = 7;
    rotate_by_gcd_like_swap(v.begin(), v.begin() + k, v.end());
    cout << " after rotate: ";
    for (auto x: v) cout << x << ' '; cout << '\n';
    cout << "sz = " << v.size() << ", k = " << k << '\n';
}

Answer 12

배열에 두 개의 인덱스를 유지하면 하나의 인덱스가 배열의 시작부터 배열 끝까지 시작합니다. 다른 인덱스는 마지막 MTH 위치에서 시작하고 마지막 M 요소를 여러 번 루프합니다. 항상 O (n)을 가져갑니다. 추가 공간이 필요하지 않습니다.

circleArray(Elements,M){
 int size=size-of(Elements);

 //first index
 int i1=0;

 assert(size>M)

 //second index starting from mth position from the last
 int i2=size-M;

 //until first index reaches the end
 while(i1<size-1){

  //swap the elements of the array pointed by both indexes
  swap(i1,i2,Elements);

  //increment first pointer by 1
  i1++;

  //increment second pointer. if it goes out of array, come back to
  //mth position from the last
  if(++i2==size) i2=size-M;

 }
}

Answer 13

Java 구현에 관심이 있으시면 다음을 참조하십시오.

진주 프로그래밍 : 원형 왼쪽/오른쪽 시프트 작동

Answer 14

static int [] shift(int arr[], int index, int k, int rem)
{
    if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length)
    {
        return arr;
    }

    int temp = arr[index];

    arr = shift(arr, (index+k) % arr.length, k, rem - 1);

    arr[(index+k) % arr.length] = temp;

    return arr;
}

Answer 15

루비 예 :

def move_cyclic2 array, move_cnt
  move_cnt = array.length - move_cnt % array.length 
  if !(move_cnt == 0 || move_cnt == array.length)            
    array.replace( array[move_cnt..-1] + array[0...move_cnt] )  
  end   
end

Answer 16

이론적으로 가장 빠른 것은 다음과 같은 루프입니다.

if (begin != middle && middle != end)
{
    for (i = middle; ; )
    {
        swap(arr[begin++], arr[i++]);
        if (begin == middle && i == end) { break; }
        if (begin == middle) { middle = i; }
        else if (i == end) { i = middle; }
    }
}

실제로, 당신은 그것을 프로파일하고보아야합니다.

Answer 17

다음은 Nother One (C ++)입니다.

void shift_vec(vector<int>& v, size_t a)
{
    size_t max_s = v.size() / a;
    for( size_t s = 1; s < max_s; ++s )
        for( size_t i = 0; i < a; ++i )
            swap( v[i], v[s*a+i] );
    for( size_t i = 0; i < a; ++i )
        swap( v[i], v[(max_s*a+i) % v.size()] );
}

물론 유명한 역 3 배 솔루션만큼 우아하지는 않지만 기계에 따라 Similary Fast.

Answer 18

circleArray 약간의 오류가 있으며 모든 경우에 작동하지 않습니다!

루프는 계속되어야합니다 while i1 < i2 아니다 i1 < last - 1.

void Shift(int* _array, int _size, int _moves)
{
    _moves = _size - _moves;
    int i2 = _moves;
         int i1 = -1;
         while(++i1 < i2)
    {
        int tmp = _array[i2];
        _array[i2] = _array[i1];
        _array[i1] = tmp;
        if(++i2 == _size) i2 = _moves;
    }
}

Answer 19

내 친구가 농담을하는 동안 한 친구가 배열을 전환하는 방법을 물었습니다. 저는이 솔루션을 생각해 냈습니다 (Ideone 링크 참조). 이제 나는 당신의 것을 보았습니다.

구경하다 여기.

#include <iostream>

#include <assert.h>

#include <cstring>

using namespace std;

struct VeryElaboratedDataType
{
    int a;
    int b;
};

namespace amsoft
{
    namespace inutils
    {
        enum EShiftDirection
        {
            Left,
            Right
        };
template 
<typename T,size_t len>
void infernalShift(T infernalArray[],int positions,EShiftDirection direction = EShiftDirection::Right)
{
    //assert the dudes
    assert(len > 0 && "what dude?");
    assert(positions >= 0 && "what dude?");

    if(positions > 0)
    {
    ++positions;
    //let's make it fit the range
    positions %= len;

    //if y want to live as a forcio, i'l get y change direction by force
    if(!direction)
    {
        positions = len - positions;
    }

    // here I prepare a fine block of raw memory... allocate once per thread
    static unsigned char WORK_BUFFER[len * sizeof(T)];
    // std::memset (WORK_BUFFER,0,len * sizeof(T));
    // clean or not clean?, well
    // Hamlet is a prince, a prince does not clean

    //copy the first chunk of data to the 0 position
    std::memcpy(WORK_BUFFER,reinterpret_cast<unsigned char *>(infernalArray) + (positions)*sizeof(T),(len - positions)*sizeof(T));
    //copy the second chunk of data to the len - positions position
    std::memcpy(WORK_BUFFER+(len - positions)*sizeof(T),reinterpret_cast<unsigned char *>(infernalArray),positions * sizeof(T));

    //now bulk copy back to original one
    std::memcpy(reinterpret_cast<unsigned char *>(infernalArray),WORK_BUFFER,len * sizeof(T));

    }

}
template 
<typename T>
void printArray(T infernalArrayPrintable[],int len)
{
        for(int i=0;i<len;i++)
    {
        std::cout << infernalArrayPrintable[i] << " ";
    }
    std::cout << std::endl;

}
template 
<>
void printArray(VeryElaboratedDataType infernalArrayPrintable[],int len)
{
        for(int i=0;i<len;i++)
    {
        std::cout << infernalArrayPrintable[i].a << "," << infernalArrayPrintable[i].b << " ";
    }
    std::cout << std::endl;

}
}
}




int main() {
    // your code goes here
    int myInfernalArray[] = {1,2,3,4,5,6,7,8,9};

    VeryElaboratedDataType myInfernalArrayV[] = {{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{8,8},{9,9}};
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
    amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4);
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
    amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4,amsoft::inutils::EShiftDirection::Left);
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
    amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,10);
    amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));


    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
    amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4);
    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
    amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4,amsoft::inutils::EShiftDirection::Left);
    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
    amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,10);
    amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));

    return 0;
}

Answer 20

이 방법은이 작업을 수행합니다.

public static int[] solution1(int[] A, int K) {
    int temp[] = new int[A.length];

    int count = 0;

    int orignalItration = (K < A.length) ? K :(K%A.length); 


    for (int i = orignalItration; i < A.length; i++) {
        temp[i] = A[count++];
    }
    for (int i = 0; i < orignalItration; i++) {
        temp[i] = A[count++];
    }

    return temp;
}

Answer 21

@isaacturner와 유사하며 불필요한 복사로 인해 우아하지는 않지만 구현은 상당히 짧습니다.

아이디어 -A의 대상에있는 요소 B와 함께 인덱스 0의 요소를 스왑 요소 A. 이제 B는 첫 번째입니다. 대상이있는 요소 C로 교체하십시오. 대상이 0이 될 때까지 계속하십시오.

가장 큰 일반적인 제수가 1이 아닌 경우 아직 끝나지 않았습니다. 계속 스와핑해야하지만 이제 시작점과 종료점에서 인덱스 1을 사용해야합니다.

시작 위치가 GCD가 아닐 때까지 계속하십시오.

int gcd(int a, int b) => b == 0 ? a : gcd(b, a % b);

public int[] solution(int[] A, int K)
{
    for (var i = 0; i < gcd(A.Length, K); i++)
    {
        for (var j = i; j < A.Length - 1; j++)
        {
            var destIndex = ((j-i) * K + K + i) % A.Length;
            if (destIndex == i) break;
            var destValue = A[destIndex];
            A[destIndex] = A[i];
            A[i] = destValue;
        }
    }

    return A;
}

Answer 22

다음은 Java의 솔루션이 100% 작업 점수와 Codility에서 100% 정확성을 얻었습니다.

class Solution {
    public int[] solution(int[] A, int K) {
        // write your code in Java SE 8
        if (A.length > 0)
        {
            int[] arr = new int[A.length];
            if (K > A.length)
                K = K % A.length;

            for (int i=0; i<A.length-K; i++)
                arr[i+K] = A[i];

            for (int j=A.length-K; j<A.length; j++)
                arr[j-(A.length-K)] = A[j];

            return arr;
        }
        else
            return new int[0];
    }
}

두 가지를 보더라도 주목하십시오 for 루프, 전체 배열의 반복은 한 번만 수행됩니다.

Answer 23

왼쪽으로 이동하기위한 Swift 4 버전.

func rotLeft(a: [Int], d: Int) -> [Int] {

   var result = a
   func reverse(start: Int, end: Int) {
      var start = start
      var end = end
      while start < end {
         result.swapAt(start, end)
         start += 1
         end -= 1
      }
   }

   let lenght = a.count
   reverse(start: 0, end: lenght - 1)
   reverse(start: lenght - d, end: lenght - 1)
   reverse(start: 0, end: lenght - d - 1)
   return result
}

예를 들어 입력 배열 인 경우 a = [1, 2, 3, 4, 5], 왼쪽 시프트 오프셋입니다 d = 4, 그러면 결과가 될 것입니다 [5, 1, 2, 3, 4]