M 位置のサークル シフト N サイズ配列の最速アルゴリズム
-
22-08-2019 - |
質問
M 位置の円シフト配列の最速アルゴリズムは何ですか?
例えば、 [3 4 5 2 3 1 4]
シフト M = 2 の位置は次のようになります。 [1 4 3 4 5 2 3]
.
どうもありがとう。
解決
あなたが(配列が指定されていたので)O(n)の時間と余分なメモリ使用量をしたい場合は、「真珠第2版プログラミング」ジョン・ベントレーの著書からのアルゴリズムを使用します。それは二回、すべての要素を交換します。しかし、リンクされたリストを使用するのと同じ速さではないが、少ないメモリを使用して、概念的には単純です。
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の包括的に要素の順序を逆にする。
他のヒント
これは表現の問題です。整数型変数として現在のインデックスを維持し、ラップアラウンドしたときに知って配列利用モジュロ演算子を横断するとき。シフトは、その後のみ、アレイのサイズのまわりでそれを包む、現在のインデックスの値を変更しています。このコース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 回反転するのが最も簡単ですが、すべての要素を正確に 2 回移動するため、O(N) 時間と O(1) スペースがかかります。O(N) 時間、O(1) 空間でも、各要素を 1 回だけ移動する配列を循環シフトすることができます。
アイデア
長さの配列をサークルシフトできます N=9
による M=1
1 サイクルで:
tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;
で、もし N=9
, M=3
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;
各要素は 1 回読み取られ、1 回書き込まれます。
変速の図 N=9, M=3
最初のサイクルは黒で表示され、数字は操作の順序を示します。2 番目と 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 分の 1 に減らすオーバーヘッドは価値があります。参照: http://www.geeksforgeeks.org/array-rotation/
ポインタでそれを設定し、それはほとんどの時間を要します。次の、そして「最後」の各要素点(ラストはありません。結局、あなたはそれが円形であると言いました)最初指します。一つの「スタート」(最初の要素)、そしておそらく長さへのポインタ、あなたはあなたの配列を持っています。さて、あなたのシフトを行うために、あなただけの円に沿って、あなたの開始ポインタを歩きます。
良いアルゴリズムを尋ね、あなたは賢明なアイデアを得ます。 の最速のために掲載して、あなたは奇妙なアイデアを得る!
このアルゴリズムは、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;
}
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に適しています。
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];
}
}
}
非常にシンプルなソリューションを提供します。これは、ここで私は、同じサイズまたは元に一時配列を使用し、最後に元の変数にアタッチする、非常に高速な方法です。 この方法の使用は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;
あなたが使用するデータ構造に応じて、O(1)でそれを行うことができます。私は、最速の方法は、リンクリストの形で配列を保持し、エントリへの「ポインタ」への配列に「インデックス」の間で変換することができ、ハッシュテーブルを持つことだと思います。あなたはOで関連頭と尾を見つけることができますこの方法は、(1)、およびO(1)で再接続を行う(とOのスイッチの後にハッシュテーブルを更新(1))。もちろん、これは非常に「厄介な」解決策になるだろうが、あなたが興味を持っているすべてを行いますシフトの速さ、であれば(配列の長い挿入して、ルックアップの費用に、それはまだ(O残ります1))
あなたは純粋な配列のデータを持っている場合、私は考えていないあなたはO(n)を回避することができます。
ワイズコーディング、それはあなたが使用している言語によって異なります。
Pythonでは、たとえば、あなたは "スライス" は、それが(nはシフトの大きさであると仮定)ことができます:
result = original[-n:]+original[:-n]
(...私は、ハッシュ検索が理論的にあることを知っていないO(1)私たちは、少なくとも私はそう願って、ここではなく、理論的実践的です)。
このは、円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];
}
}
}
のここでは代わりに、簡単かつ効率的な一般的に、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';
}
1つのインデックスは、配列の最後に配列の先頭から始まり、配列への2つのインデックスを保管してください。別の指標は、最後から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;
}
}
これを参照してください。
<のhref = "http://programmingpearls.blogspot.com/search?updated-min=2011-01-01T00%3A00%3A00-08%3A00&updated-max=2012-01-01T00%3A00%3A00- 08パーセント3A00&MAX-結果= 2" のrel = "nofollowを">プログラミング真珠:循環左/右シフト操作する
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;
}
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
理論的には、最速の1は、このようなループです。
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; }
}
}
実際には、あなたがそれをプロファイルし、表示されるはずです。
ここNotherのの一方(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()] );
}
はもちろん、それは有名な逆の三倍液ほどエレガントではありませんが、マシンによってはそれができる similary速くするます。
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;
}
}
私の友人は、どのように配列をシフトするために私に尋ねた冗談ながら、私は(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;
}
このメソッドは、この作業を行います。
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;
}
不必要なコピーのためにその優雅な@IsaacTurnerと同様にしていないが、実装はかなり短いです。
アイデアは - A.今Bの宛先に着座要素Bとインデックス0のスワップエレメントAが最初です。宛先が0でなくなるまで続けB.先に座っ素子Cでそれを交換します。
あなたはスワップ継続する必要があるが、今お使いの始点と終点のインデックス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;
}
ここでくれCodilityで100%のタスクのスコアと100%の正確さを持ってJavaで私の解決策はあります:
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];
}
}
2つのfor
ループを見てもかかわらず、全体のアレイ上の反復は一度だけ行われること注
スイフト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]
する結果