移位算法：面試和做項目必會

最近在項目里需要對采樣數(shù)據(jù)做移位操作，研究了下幾個移位操作算法，今天通過本文分享給大家。我們知道位運算中有循環(huán)左移和右移運算，但是，對于數(shù)組，鏈表，Vecter容器等數(shù)據(jù)結(jié)構(gòu)，就需要自己實現(xiàn)移位算法了，本文以數(shù)組作為例子，和大家一起學(xué)習(xí)幾種移位算法的實現(xiàn)。希望給大家在平時項目中能起到拋磚引玉的作用。

我們先設(shè)有一個數(shù)組data，數(shù)組data的大小為5，其值分別為{0，1，2，3，4}，需要分別對數(shù)組data循環(huán)右移3個元素和循環(huán)向左移動3個元素。

第一種方法

首先，我們來看第一種方法，對于循環(huán)右移3個元素，我們可以分解成：先對每個元素都向右移動一個元素，其中最后一個元素需要放到數(shù)組的開頭位置，會得到一個新的數(shù)組，然后，用新的數(shù)組再做同樣的操作，如此循環(huán)3次，即可實現(xiàn)循環(huán)右移3個元素。

同樣的對于循環(huán)左移3個元素，也可這樣分解，只不過需要將每個元素需要先向左移動，其中開頭的元素就要放到末尾，得到的新數(shù)組。然后，再做同樣的操作3次。

下面是C++代碼實現(xiàn)，函數(shù)中參數(shù)data是需要循環(huán)操作的數(shù)組，參數(shù)size是數(shù)據(jù)的大小，參數(shù)moveStep是移動元素的個數(shù)，大于0表示向右移，小于0表示向左移。

void cycleShift1(int data[], int size, int moveStep){

auto rightMoveOnce = [&](int data[], int size)
{
int temp = data[size-1];
for(int i=size-1; i>0; i--)
{
data[i]=data[i-1];
}
data[0] = temp;
};

auto leftMoveOnce = [&](int data[], int size)
{
int temp = data[0];
for(int i=1; i<size; i++)
{
data[i-1]=data[i];
}
data[size-1] = temp;
};

moveStep %= size;
if(moveStep>0)
{
while(moveStep--)
{
rightMoveOnce(data, size);
}
}
else
{
while(moveStep++)
{
leftMoveOnce(data, size);
}
}
}

第二種方法

上面的第一種方法是最直觀的的一種方法，不過，它的時間復(fù)雜度相對高一些。我們可以通過使用空間換取時間的方法對其進(jìn)行優(yōu)化。

這種方法需要創(chuàng)建一個新的數(shù)組作為臨時輔助，以右移為例：

第一步，需要將結(jié)尾的三個數(shù)據(jù){2,3,4}存放到這個新的輔助數(shù)組中。

第二步，將開頭的兩個數(shù)據(jù){0,1}向右移動3個元素位置。

第三步，將輔助數(shù)組的數(shù)據(jù){2,3,4}放到開頭。

經(jīng)過上面三步之后，即可得到最終的結(jié)果。

類似的，對于循環(huán)左移，就需要將開頭的三個數(shù)據(jù){0,1,2}存放到輔助數(shù)組中，結(jié)尾的兩個數(shù)據(jù){3,4}，向左移動3個元素位置。最后，再將輔助數(shù)組中的3個數(shù)據(jù)放到結(jié)尾。

下面是代碼實現(xiàn)：

void cycleShift2(int data[], int size, int moveStep)
{
moveStep %= size;
if(moveStep>0)
{
int temp[moveStep] = {0};
for(int i = 0; i < moveStep; i++)
{
temp[i] = data[size - moveStep + i];
}

for(int i = 0; i < size - moveStep; i++)
{
data[size - i - 1] = data[size - moveStep - 1 - i];
}

for(int i = 0; i < moveStep; i++)
{
data[i] = temp[i];
}
}
else
{
moveStep *= -1;
int temp[moveStep] = {0};

for(int i = 0; i < moveStep; i++)
{
temp[i] = data[i];
}

for(int i = 0; i < size - moveStep; i++)
{
data[i] = data[moveStep + i];
}

for(int i=0; i < moveStep; i++)
{
data[size - moveStep + i] = temp[i];
}
}
}

第三種方法

我們還可以通過一個小技巧來實現(xiàn)循環(huán)移動的功能。

先看循環(huán)右移，首先，我們需要將數(shù)組分成兩部分，第一部分是{0，1}，第二部分是{2，3，4}。

第一步，將{0,1}做個翻轉(zhuǎn)，得到{1,0}

第二步，將{2,3,4}做個翻轉(zhuǎn)，得到{4,3,2}

第三步，將{1,0,4,3,2}當(dāng)作一個整體，再次翻轉(zhuǎn)，得到{2,3,4,0,1}。

三次翻轉(zhuǎn)之后，就可得到我們想要的結(jié)果。

同樣的對于循環(huán)左移，就需要將數(shù)組分成{0,1,2}和{3,4}兩部分。經(jīng)過三步的翻轉(zhuǎn)，可以得到循環(huán)左移的結(jié)果。

下面是三次翻轉(zhuǎn)的代碼實現(xiàn)：

void cycleShift3(int data[], int size, int moveStep)
{

auto reverse = [&](int data[], int startIndex, int endIndex)
{
for (; startIndex < endIndex; startIndex++, endIndex--)
{
double temp = data[endIndex];
data[endIndex] = data[startIndex];
data[startIndex] = temp;
}
};

moveStep %= size;

if(moveStep > 0) //Right shift
{
reverse(data, 0, size - moveStep - 1);
reverse(data, size - moveStep, size - 1);
}
else //Left shift
{
reverse(data, 0, 0 - moveStep - 1);
reverse(data, 0 - moveStep, size - 1);
}

reverse(data, 0, size - 1);
}

最后

上面和大家一起學(xué)習(xí)了三種移位算法的實現(xiàn)，最后我們寫個小程序驗證一下三種算法的結(jié)果。

void printData(int data[], int size)
{
for(int i=0; i < size; i++)
{
std::cout << data[i] << " ";
}
std::cout << std::endl;
}

int main()
{

int data1_1[] = {0,1,2,3,4};
int data1_2[] = {0,1,2,3,4};
int data2_1[] = {0,1,2,3,4};
int data2_2[] = {0,1,2,3,4};
int data3_1[] = {0,1,2,3,4};
int data3_2[] = {0,1,2,3,4};
int size = 5;
int moveStep = 3;

std::cout << "-------------" << std::endl;
cycleShift1(data1_1, size, moveStep);
cycleShift1(data1_2, size, -1*moveStep);
printData(data1_1,size);
printData(data1_2,size);

std::cout << "-------------" << std::endl;
cycleShift2(data2_1, size, moveStep);
cycleShift2(data2_2, size, -1*moveStep);
printData(data2_1, size);
printData(data2_2, size);

std::cout << "-------------" << std::endl;
cycleShift3(data3_1, size, moveStep);
cycleShift3(data3_2, size, -1*moveStep);
printData(data3_1, size);
printData(data3_2, size);

}

感謝大家的閱讀，以上就是移位算法的全部內(nèi)容，希望大家從中能有所收獲，看完可以收藏以便查看，也記得轉(zhuǎn)發(fā)、點贊和點亮再看哈！感謝支持！