本篇文章是一篇關(guān)于數(shù)組空間的帖子

???? ? ? 目題要求如下：給定一列數(shù)組，找出在這個數(shù)組中同相據(jù)數(shù)涌現(xiàn)置位的最大差值，例如：1, 2, 3, 4, 1, 1, 7, 4， max(1) = 5, max(2) = 0, max(4) = 4;

???? ? ? 給出兩種法方，一種是應(yīng)用hash，種這法方比擬有局限性，首先，如果數(shù)組中的某一個值比擬大的話，應(yīng)用hash就會比擬費浪空間，定義這樣的據(jù)數(shù)結(jié)構(gòu)：

???? typedef struct data_s? {

???? int value;

???? int start;

???? int end;

???? }

???? 設(shè)定這樣一個hash數(shù)組，然后遍歷數(shù)組，記載數(shù)字第一次涌現(xiàn)的置位并堅持穩(wěn)定，同相數(shù)字如果后之再涌現(xiàn)，則更新?lián)?shù)結(jié)構(gòu)中的end，這樣數(shù)組被遍歷一遍后之，有所數(shù)字第一次涌現(xiàn)的置位和最后一次涌現(xiàn)的置位都會被記載下來，應(yīng)用的時間復(fù)雜度和空間復(fù)雜度均是O(N)，但是種這法方局限性比擬大，就是空間的損耗，和不能判斷要分配多少空間。既然我們不能態(tài)靜的分配定一的空間來記載這些信息，我們可以動態(tài)的分配，應(yīng)用二叉查找樹可以滿意這一點。但是空間復(fù)雜度和時間復(fù)雜度有點高，時間復(fù)雜度是O(n*logn)， 空間復(fù)雜度是O(n)。但是種這做法比用hash好的多，在不要求速快決解提問題的情況下應(yīng)用二叉查找樹是一個不錯的擇選，上面給出碼代，如果有不正確的地方，敬請指出：

????

    #include<iostream>

using namespace std;



typedef struct data_s {

	int value;

	int start;

	int end;

}data_t;



typedef struct tree_node_s {

	data_t data;

	struct tree_node_s *lchild;

	struct tree_node_s *rchild;

}tree_node_t, *BSTree;



int tree_search(BSTree T, int value, tree_node_t **p, tree_node_t *f) {

	if (NULL == T) {

		*p = f;

		return 0;

	}

	if (value == T->data.value) {

		*p = T;

		return 1;

	} else if (value < T->data.value) {

		return tree_search(T->lchild, value, p, T);

	} else {

		return tree_search(T->rchild, value, p, T);

	}

}



void tree_insert(BSTree *T, int value, int index) {

	tree_node_t *p = NULL;

	if (!tree_search(*T, value, &p, NULL)) {

		tree_node_t *temp = (tree_node_t*)malloc(sizeof(tree_node_t));

		temp->data.value = value;

		temp->data.start = index;

		temp->data.end   = index;

		temp->lchild = NULL;

		temp->rchild = NULL;

		if (NULL == (*T)) {

			*T = temp;

		} else if (value < p->data.value) {

			p->lchild = temp;

		} else {

			p->rchild = temp;

		}

	} else {

		p->data.end = index;

	}

}



void tree_traverse(BSTree T) {

	if (T) {

		tree_traverse(T->lchild);

		cout << "value:" << T->data.value << " start at:" << T->data.start <<

			" end at:" << T->data.end << " distance:" << T->data.end - T->data.start << endl;

		tree_traverse(T->rchild);

	}

}



void tree_destroy(BSTree *T) {

	if (*T) {

		tree_destroy(&(*T)->lchild);

		tree_destroy(&(*T)->rchild);

		free((*T));

	}

}



int main(int argc, char *argv[]) {

	int i;

	BSTree T = NULL;

	int arr[] = {1, 2, 3, 4, 1, 1, 7, 4};

	int len = sizeof(arr) / sizeof(int);

	for (i = 0; i < len; i++) {

		tree_insert(&T, arr[i], i);

	}

	tree_traverse(T);

	tree_destroy(&T);

	cin.get();

	return 0;

}
  

文章結(jié)束給大家分享下程序員的一些笑話語錄： 一程序員告老還鄉(xiāng)，想安度晚年，于是決定在書法上有所造詣。省略數(shù)字……，準(zhǔn)備好文房4寶，揮起毛筆在白紙上鄭重的寫下：Hello World

數(shù)組空間Given a sequence of numbers (or array).Find the maximum distance between all the same numbers.