Given a sequence of numbers (or array).Find the maximum dist

  題目要求如下：給定一列數組，找出在這個數組中相同數據出現位置的最大差值，例如：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好的多，在不要求快速解決提問題的情況下應用二叉查找樹是一個不錯的選擇，下面給出代碼，如果有不正確之處，敬請指出：

[cpp]
#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; 
}