Самый быстрый алгоритм для сдвига по кругу массива размером N для M позиции

Question

Какой самый быстрый алгоритм для массива смещения окружности для M позиций?
Например, [3 4 5 2 3 1 4] сдвиг M = 2 положения должен быть [1 4 3 4 5 2 3].

Большое спасибо.

Answer 1

Если вам нужно O (n) времени и никакого дополнительного использования памяти (поскольку был указан array), используйте алгоритм из книги Джона Бентли "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

Это просто вопрос репрезентации.Сохраняйте текущий индекс как целочисленную переменную и при обходе массива используйте оператор modulo, чтобы знать, когда нужно выполнить обход.В этом случае сдвиг означает только изменение значения текущего индекса, обтекая его вокруг размера массива.Это, конечно, 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

Первый цикл показан черным цветом с цифрами, указывающими порядок операций.Второй и третий циклы показаны серым цветом.

Требуемое количество циклов равно Наибольший общий Делитель (НОД) из 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

Настройте его с помощью указателей, и это почти не займет времени.Каждый элемент указывает на следующий и "последний" (последнего нет;в конце концов, вы сказали, что она круглая) указывает на первую.Один указатель на "начало" (первый элемент) и, возможно, на длину, и у вас есть свой массив.Теперь, чтобы выполнить свою смену, вы просто проводите указателем start по кругу.

Попросите хороший алгоритм, и вы получите разумные идеи.Просите о самый быстрый, и у тебя возникают странные идеи!

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

Этот код хорошо работает даже при отрицательном сдвиге 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,6,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

Храните два индекса к массиву, один индекс начинается от начала массива до конца массива.Другой индекс начинается с M-й позиции из last и перебирает последние 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

Пример Ruby:

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

Вот еще один вариант (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()] );
}

Конечно, это далеко не так элегантно, как знаменитое трехкратное обратное решение, но в зависимости от машины оно может быть аналогично быстро.

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 с индексом 0 на элемент B, который находится в пункте назначения A.Теперь B на первом месте.Замените его элементом C, который находится в пункте назначения B.Продолжайте до тех пор, пока пункт назначения не будет равен 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% Оценку задачи и 100% корректность при Codility:

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]