本篇文章是一篇關(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;

???? ? ? 給出兩種法方，一種是應用hash，種這法方比擬有局限性，首先，如果數(shù)組中的某一個值比擬大的話，應用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)的置位都會被記載下來，應用的時間復雜度和空間復雜度均是O(N)，但是種這法方局限性比擬大，就是空間的損耗，和不能判斷要分配多少空間。既然我們不能態(tài)靜的分配定一的空間來記載這些信息，我們可以動態(tài)的分配，應用二叉查找樹可以滿意這一點。但是空間復雜度和時間復雜度有點高，時間復雜度是O(n*logn)， 空間復雜度是O(n)。但是種這做法比用hash好的多，在不要求速快決解提問題的情況下應用二叉查找樹是一個不錯的擇選，上面給出碼代，如果有不正確的地方，敬請指出：

????

    #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ù)字……，準備好文房4寶，揮起毛筆在白紙上鄭重的寫下：Hello World

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