最近做東西的時(shí)候出現(xiàn)這么一個(gè)問(wèn)題，看起來(lái)很簡(jiǎn)單的：
#define LARGE_SIZE 1024
#define ELEMENT_NUM 5
class CItem
{
public:
TCHAR cID;
BYTE data[LARGE_SIZE];
};
CItem data[ELEMENT_NUM];
INT reposition[ELEMENT_NUM] = {4,2,0,3,1};
要求，根據(jù)repositon的內(nèi)容調(diào)整data的內(nèi)容，如上，把原來(lái)下標(biāo)4的元素調(diào)到0，把原來(lái)下標(biāo)2的元素調(diào)到1。
寫個(gè)算法，復(fù)雜度為O(n)，還要盡量節(jié)省空間，因?yàn)長(zhǎng)ARGE_SIZE可以很大，并且ELEMENT_NUM可能遠(yuǎn)遠(yuǎn)不止5個(gè)元素。
馬上能想到的方法就是：
INT i;
CItem *pToHandle = new CItem[ELEMENT_NUM];
memcpy(pToHandle, data, sizeof(data));
for(i=0; i<ELEMENT_NUM; i++)
{
data[i] = pToHandle[reposition[i]];
}
delete[] pToHandle;
但這不太符合節(jié)省空間的原則，有可能在一個(gè)嵌入式平臺(tái)中，new操作就會(huì)失敗。
問(wèn)題看起來(lái)是簡(jiǎn)單，但卻耗費(fèi)了我不少時(shí)間，才寫出這么一個(gè)算法，我直接貼上全部代碼：
#include "stdafx.h"
#include <Windows.h>
#define LARGE_SIZE 1024
class CItem
{
public:
TCHAR cID;
BYTE data[LARGE_SIZE];
};
#define ELEMENT_NUM 10
int _tmain(int argc, _TCHAR* argv[])
{
//Data to test
CItem allData[ELEMENT_NUM];
INT i;
for (i=0; i<ELEMENT_NUM; i++)
{
allData[i].cID = 'A' + i;
}
INT position[ELEMENT_NUM] = {5, 1, 4, 3, 6, 9, 7, 2, 0, 8};
//The result be F B E D G J H C A I
for (i=0; i<ELEMENT_NUM; i++)
{
CItem swapItem;
if (position[i]==i)
continue;
swapItem = allData[i];
INT iSeek = i;
do
{
INT iToSeekNext = position[iSeek];
allData[iSeek] = allData[iToSeekNext];
position[iSeek] = iSeek;
iSeek = iToSeekNext;
} while (position[iSeek]!=i);
allData[iSeek] = swapItem;
position[iSeek] = iSeek;
}
for (i=0; i<ELEMENT_NUM; i++)
{
_tprintf(TEXT("%c "), allData[i].cID);
}
_tprintf(TEXT("\n"));
return 0;
}
看起來(lái)寫得稍微有些亂，而且明顯用了兩層迭代，按道理說(shuō)算法復(fù)雜度應(yīng)該為O(n2)了，但再仔細(xì)分析代碼后發(fā)覺(jué)：需要調(diào)整位置的元素，只需要移動(dòng)一次，而整個(gè)遍歷過(guò)程并不會(huì)出現(xiàn)重復(fù)遍歷的情況。因此其實(shí)際復(fù)雜度應(yīng)該為O(n)，已經(jīng)是最高效了，看看還有沒(méi)別的辦法。