Schnellster Algorithmus für die Kreisverschiebung N Größe Array für M-Position
https://stackoverflow.com/questions/876293
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist der schnellste Algorithmus für Kreis für M Positionen verschieben Array?
Zum Beispiel [3 4 5 2 3 1 4] Verschiebung M = 2 Positionen sollten [1 4 3 4 5 2 3] werden.
Vielen Dank.
Lösung
Wenn Sie O (n) Zeit und keinen zusätzlichen Speicherverbrauch wollen (da Array angegeben wurde), verwenden Sie den Algorithmus von Jon Bentley Buch „Programmieren Pearls 2nd Edition“. Es tauscht alle Elemente zweimal. Nicht so schnell wie mit verkettete Listen verwendet aber weniger Speicher und ist vom Konzept her einfach.
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, start, endIndex) kehrt die Reihenfolge der Elemente von start zu endIndex, inklusive.
Andere Tipps
Es ist nur eine Frage der Repräsentation. Halten Sie den aktuellen Index als Integer-Variable und wenn die Array Verwendung Modulooperator durchqueren zu wissen, wann um zu wickeln. Shifting wird dann ändert nur den Wert des aktuellen Index, er um die Größe des Arrays Einwickeln. Dies ist natürlich O (1).
Zum Beispiel:
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;
}
Optimale Lösung
Frage bat um schnellste. dreimal Umkehren einfachsten ist aber bewegt sich jedes Element genau zweimal, nimmt O (N) Zeit und O (1) Raum. Es ist möglich, eine Anordnung umkreisen verlagern genau einmal auch in O (N) Zeit und O (1) Raum um jedes Element zu bewegen.
Idee
Wir umrunden kann eine Reihe von Länge N=9 durch M=1 mit einem Zyklus verschieben:
tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;
Und wenn N=9, M=3 wir können Kreisverschiebung mit drei Zyklen:
-
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;
Beachten Sie jedes Element einmal gelesen und einmal geschrieben.
Schema N=9, M=3 Verschiebung
Der erste Zyklus ist Show in schwarz mit Zahlen, die die Reihenfolge der Operationen. Die zweiten und dritten Zyklen sind grau dargestellt.
Die erforderliche Anzahl der Zyklen ist der größten gemeinsamen Divisor (GCD) von N und M. Wenn der GCD 3 ist, beginnen wir einen Zyklus an jedem {0,1,2}. die GCD Berechnung ist schnell mit dem binäre GGT-Algorithmus .
Beispielcode:
// 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;
}
}
-Code in C für jeden Array-Typen:
// 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;
}
Bearbeiten : Dieser Algorithmus kann auch eine bessere Leistung vs Array Umkehr haben (wenn N groß ist und M klein ist) aufgrund von Cache-Lokalität, da wir über die Anordnung in kleinen Schritten werden Looping.
Abschließender Hinweis: , wenn Ihr Array klein ist, dreifach umgekehrt ist einfach. Wenn Sie eine große Auswahl haben, lohnt es sich der Aufwand des Bearbeitens des GCD aus die Anzahl der Züge um den Faktor 2 zu reduzieren. Ref: http://www.geeksforgeeks.org/array-rotation/
es Set mit Zeigern, und es dauert fast keine Zeit. Jedes Element zeigt auf den nächsten, und dem „letzten“ (es gibt keine letzte, schließlich, Sie haben gesagt, es war circular) zeigt auf den ersten. Ein Zeiger auf den „Start“ (erstes Element), und vielleicht eine Länge, und Sie haben Ihre Array. Nun, Ihre Schicht zu tun, gehen Sie einfach Ihre Startzeiger entlang des Kreises.
Fragen Sie nach einem guten Algorithmus, und Sie vernünftige Ideen. Fordern Sie schnellste und Sie bekommen seltsame Ideen!
Dieser Algorithmus läuft in O (n) Zeit und O (1) Raum.
Die Idee ist, jede cyclische Gruppe in der Verschiebung zu verfolgen (nummeriert von nextGroup Variable).
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
Dieser Code funktioniert auch auf negative Verschiebung k
C arrayShiftRight Funktion. Wenn Verschiebung negativ ist links die Funktion verschiebt Array. Es ist für weniger Speicherverbrauch optimiert. Laufzeit ist 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];
}
}
}
Eine sehr einfache Lösung. Dies ist eine sehr schnelle Art und Weise, hier habe ich ein temporäres Array mit der gleichen Größe verwenden oder Original und auf die ursprüngliche Variable am Ende befestigen. Diese Methode Gebrauch O (n) zeitliche Komplexität und O (n) Speicherkomplexität und es ist sehr einfach zu implementieren.
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;
Abhängig von der Datenstruktur, die Sie verwenden, können Sie es in O tun (1). Ich denke, der schnellste Weg, um das Array in Form einer verketteten Liste zu halten, und eine Hash-Tabelle, das zwischen dem „Index“ in dem Array „Zeiger“ zu dem Eintrag übersetzen kann. Auf diese Weise können die entsprechenden Köpfe und Schwänze in O finden (1), und führen Sie die Wiederverbindung in O (1) (und die Hash-Tabelle nach dem Wechsel in O aktualisieren (1)). Dies würde natürlich eine sehr „chaotisch“ Lösung, aber wenn alles, was Sie interessiert sind, in der Geschwindigkeit der Verschiebung ist, die (auf Kosten längerer Einsetzen und Nachschlagen in dem Array tun, aber es bleibt immer noch O ( 1))
Wenn Sie die Daten in einem reinen Array haben, ich glaube nicht, können Sie O (n) vermeiden.
Coding-weise, es hängt davon ab, welche Sprache Sie verwenden.
In Python zum Beispiel könnten Sie "Scheibe" es (unter der Annahme n die Verschiebung Größe):
result = original[-n:]+original[:-n]
(Ich weiß, dass Hash-Lookup in der Theorie ist nicht O (1), aber wir sind hier praktisch und nicht theoretisch, zumindest hoffe ich so ...)
Dies sollte arbeiten, um eine arry zirkular zu verschieben: Input: {1, 2, 3, 5, 6, 7, 8}; Ausgangswert in Array nach den 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];
}
}
}
Dies ist eine einfache und effiziente allgemeine anstelle drehen Funktion in C ++, weniger als 10 Zeilen.
, die aus meiner Antwort auf eine andere Frage ist ein Auszug. Wie ein Array drehen?
#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';
}
Halten Sie zwei Indizes auf das Array, ein Index beginnt von Anfang des Arrays bis zum Ende des Arrays. Ein anderer Index beginnt von der M-ten Position von den letzten und Schlaufen durch die letzten M Elemente beliebig oft. Nimmt O (n) zu allen Zeiten. Kein zusätzlicher Raum erforderlich.
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;
}
}
Dieses Sehen Sie, wenn Sie in einer Java-Implementierung interessiert sind:
Programmierung Pearls: Rund links / Rechts-Verschiebung Betrieb
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-Beispiel:
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
In der Theorie der Schnellste ist eine Schleife wie folgt:
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; }
}
}
In der Praxis sollten Sie es profilieren und sehen.
Hier ist ein nother eines (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()] );
}
Natürlich ist es bei weitem nicht so elegant wie die berühmte Reverse-dreifach-Lösung, sondern in Abhängigkeit von der Maschine kann es sein, Similary schnell .
circleArray hat einige Fehler und ist nicht in allen Fällen funktioniert!
Die Schleife muss weiterhin while i1 < i2 NICHT 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;
}
}
Ein Freund von mir, während mir fragte scherzen, wie ein Array zu verschieben, kam ich mit diesen Lösungen (siehe ideone Link), jetzt habe ich gesehen, dein, jemand scheint ein wenig esoterisch.
Hier finden Sie aktuelle hier .
#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;
}
Diese Methode wird tun, um diese Arbeit:
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;
}
ähnlich wie @IsaacTurner und nicht so elegant durch unnötiges Kopieren, aber die Umsetzung ist recht kurz.
Die Idee - Swap-Element A auf dem Index 0 mit dem Element B, das auf Ziel von A. sitzt nun B erste ist. Tauschen Sie es mit dem Element C, das auf Ziel von B. sitzt weiter, bis das Ziel nicht auf 0 ist.
Wenn der größte gemeinsame Teiler nicht 1 ist dann bist du noch nicht fertig -. Sie tauschen fortsetzen müssen, aber jetzt mit Index 1 an Ihrem Anfangs- und Endpunkt
Weiter, bis die Ausgangsposition nicht die GCD ist.
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;
}
Hier ist meine Lösung in Java, die mir 100% Aufgabe Score und 100% Correctness bei Codility bekam:
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];
}
}
Beachten Sie, dass zwei for Schleifen trotz zu sehen, die Iteration auf dem gesamten Array nur einmal durchgeführt wird.
Swift-4-Version für das Verschieben Array links.
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
}
Wenn beispielsweise Eingangsarray ist a = [1, 2, 3, 4, 5] und Linksverschiebung versetzt ist d = 4, dann werden [5, 1, 2, 3, 4] Result
