Какой самый быстрый алгоритм для массива смещения круга для m позиций?
Например, [3 4 5 2 3 1 4] сдвиг m = 2 положения должны быть [1 4 3 4 5 2 3]
Спасибо большое
Самый быстрый алгоритм для массива размера круга N для M позиции
Ответ 1
Если вы хотите время O (n) и дополнительное использование памяти (поскольку массив был указан), используйте алгоритм из книги Джона Бентли "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 включительно.
Ответ 2
Это просто вопрос представления. Сохраняйте текущий индекс как целочисленную переменную, и при обходе массива используйте оператор modulo, чтобы знать, когда его нужно обернуть. Shifting только меняет значение текущего индекса, обертывая его вокруг размера массива. Это, конечно, 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;
}
Ответ 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, мы можем сдвинуть круг с тремя циклами:
-
tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp; -
tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp; -
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/
Ответ 4
Настройте его с помощью указателей, и это займет почти нет времени. Каждый элемент указывает на следующий, а "последний" (нет последнего, ведь вы сказали, что он круговой) указывает на первое. Один указатель на "начало" (первый элемент) и, возможно, длину, и у вас есть массив. Теперь, чтобы сделать вашу смену, вы просто пропустите указатель начала по кругу.
Попросите хороший алгоритм, и вы получите разумные идеи. Спросите быстрее, и вы получите странные идеи!
Ответ 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;
}
Ответ 6
В зависимости от используемой структуры данных вы можете сделать это в O (1). Я думаю, что самый быстрый способ - держать массив в виде связанного списка и иметь хеш-таблицу, которая может переводить между "индексом" в массиве на "указатель" на запись. Таким образом, вы можете найти соответствующие главы и хвосты в O (1) и выполнить повторное соединение в O (1) (и обновить хэш-таблицу после переключения в O (1)). Это, конечно, было бы очень "грязным" решением, но если все, что вас интересует, это скорость сдвига, что будет делать (за счет более длинной вставки и поиска в массиве, но он все равно останется O ( 1))
Если у вас есть данные в чистом массиве, я не думаю, что вы можете избежать O (n).
Кодирование, это зависит от того, какой язык вы используете.
В Python, например, вы можете "нарезать" его (предположим, что n - это размер сдвига):
result = original[-n:]+original[:-n]
(Я знаю, что хэш-поиск в теории не O (1), но мы здесь практические и не теоретические, по крайней мере, я надеюсь, что так...)
Ответ 7
Функция C arrayShiftRight. Если сдвиг отрицательный, функция сдвигает массив влево. Он оптимизирован для меньшего использования памяти. Время работы - 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];
}
}
}
Ответ 8
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
Ответ 9
Это должно работать для смещения кругового движения: Вход: {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];
}
}
}
Ответ 10
Сохраняйте два индекса в массиве, один индекс начинается с начала массива до конца массива. Другой индекс начинается с M-й позиции от последней и циклически проходит через последние 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;
}
}
Ответ 11
circleArray имеет некоторые ошибки и не работает во всех случаях!
Цикл должен продолжаться while i1 < i2 NOT 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;
}
}
Ответ 12
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;
}
Ответ 13
Смотрите это, если вас интересует реализация Java:
Программирование жемчуга: круговая левая/правая операция переключения
Ответ 14
Пример 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
Ответ 15
В теории, самый быстрый из них такой петли:
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; }
}
}
На практике вы должны просмотреть его и посмотреть.
Ответ 16
Вот еще один (С++):
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()] );
}
Конечно, это не так элегантно, как знаменитое обратное трехрежимное решение, но в зависимости от машины это может быть аналогично быстро.
Ответ 17
Один мой друг, шутя, спросил меня, как сменить массив, я придумал это решение (см. ссылку 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 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;
}
Ответ 18
Этот метод будет выполнять эту работу:
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;
}
Ответ 19
Вот простая и эффективная общая функция rotate в С++, менее 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';
}