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

제목 은 다음 과 같 습 니 다. 배열 을 지정 하고 이 배열 에서 같은 데이터 에 나타 난 위치의 최대 차 이 를 찾 습 니 다. 예 를 들 어 1, 2, 3, 4, 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;
}