本篇文章是一篇關于數組空間的帖子

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

???? ? ? 給出兩種法方，一種是應用hash，種這法方比擬有局限性，首先，如果數組中的某一個值比擬大的話，應用hash就會比擬費浪空間，定義這樣的據數結構：

???? typedef struct data_s? {

???? int value;

???? int start;

???? int end;

???? }

???? 設定這樣一個hash數組，然后遍歷數組，記載數字第一次涌現的置位并堅持穩定，同相數字如果后之再涌現，則更新據數結構中的end，這樣數組被遍歷一遍后之，有所數字第一次涌現的置位和最后一次涌現的置位都會被記載下來，應用的時間復雜度和空間復雜度均是O(N)，但是種這法方局限性比擬大，就是空間的損耗，和不能判斷要分配多少空間。既然我們不能態靜的分配定一的空間來記載這些信息，我們可以動態的分配，應用二叉查找樹可以滿意這一點。但是空間復雜度和時間復雜度有點高，時間復雜度是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;

}
  

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

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