這是算法導論習題11.1-4。
具體題目如下：
解決該題目的要點：
1.由于是無窮大的數組，所以無法事先初始化該數組。
2.所提供的方案必須是O（1）。
3.使用的額外空間只能是O（n），這樣平均到每一個項上的空間都是O（1）。
一時之間好像沒有一點頭緒，在幾個群里面發問了，網上搜了很久也沒有找到答案，后面一群里有個高人給了個鏈接，里面有解法。
鏈接地址：http://www.cnblogs.com/flyfy1/archive/2011/03/05/1971502.html，這篇文章里面另外給了個pdf，這個pdf估計是解法
的來源。偽代碼寫得不給力，不過前面的英文描述卻很清晰。說實話，這個方法很巧妙。
解法大概的意思如下：
開一個額外的數組A，A[0]表示A數組元素的數目(當然不包括A[0]本身)，A[i]代表插入的第i個元素的key。假設原來的無窮大數組用Huge
表示，如果Huge[i](直接尋址，假設i就是key)有效，則表示其在A數組中的索引。那么如果A[Huge[i]] == i 而且 Huge[i] <= A[0] &&
Huge[i] > 0，則表示i這個位置已經有元素插入了。
插入：A[0]++;A[A[0]] = key; Huge[key] = A[0];
搜索: A[Huge[i]] == i && Huge[i] <= A[0] && Huge[i] > 0 則return true;
刪除: 先搜索該位置是否有元素, 如果Search(key)成功，則先把Huge[ A[A[0]] ] = Huge[key]，
然后交換A[A[0]]和A[Huge[key]]，A[0]--即可。
所有操作都是O（1），平均到每一個項，使用的空間都是O（1）。
我用代碼實現的模擬如下：
#include <stdio.h>
#include <vector>
#include <algorithm>
using std::swap;
using std::vector;
#define INF (100)
int nHuge[INF];
//假設這個巨大的數組是無法初始化的
vector<
int> vA;
void Init()
{
vA.push_back(0);
//添加A[0]表示元素的數目
}
void Insert(
int nKey)
{
vA[0]++;
nHuge[nKey] = vA[0];
vA.push_back(nKey);
}
bool Search(
int nKey)
{
if (nHuge[nKey] > 0 && nHuge[nKey] <= vA[0] && vA[nHuge[nKey]] == nKey)
{
return true;
}
return false;
}
void Delete(
int nKey)
{
if (Search(nKey))
{
nHuge[ vA[vA[0]] ] = nHuge[nKey];
//將huge的最后一個元素中存儲的A數組的索引改為nHuge[nKey]
swap(vA[vA[0]], vA[nHuge[nKey]]);
//交換key
--vA[0];
vA.erase(vA.end() - 1);
}
}
#define MAX (10)
int main()
{
Init();
int i;
for (i = 0; i < MAX; ++i)
{
Insert(i);
}
for (i = 0; i < MAX; ++i)
{
printf("Search:%d %s\n", i, Search(i) ==
true? "Success" : "Failure");
}
printf("\n");
Delete(4);
Delete(9);
Delete(1);
for (i = 0; i < MAX * 2; ++i)
{
printf("Search:%d %s\n", i, Search(i) ==
true? "Success" : "Failure");
}
return 0;
}