《Cracking the Coding Interview》——第11章：排序和搜索——題目8

2014-03-21 22:23

題目：假設你一開始有一個空數組，你在讀入一些整數并將其插入到數組中，保證插入之后數組一直按升序排列。在讀入的過程中，你還可以進行一種操作：查詢某個值val是否存在于數組中，并給出這個元素在數組中的位置(如果有多個的重復元素話，給出最小的下標)。

解法：書上的原題不是這么描述的，但我覺得用這種插入排序的說法更好理解。雖然說是數組，但實際上既可以用真的數組來模擬這一過程，也可以用一棵二叉搜索樹來做。我的實現是用二叉搜索樹，每個節點里除了記錄元素的值之外，還記錄它的左子樹有多少個點。這樣在樹里面也能進行對數級的查找。其實，用數組直接模擬的話，代碼應該更好寫的。

代碼：

// 11.8 Given an array of integers, find out for a given value, how many integers are there in the array, that are no greater than the value.
// If the value is not in the array, return -1 instead.
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

struct TreeNode {
    int val;
    int count;
    int count_left;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int _val = 0): val(_val), count(1), count_left(0), left(nullptr), right(nullptr) {};
};

void insertNode(TreeNode *&root, int val)
{
    if (root == nullptr) {
        root = new TreeNode(val);
    } else if (val == root->val) {
        ++(root->count);
    } else if (val < root->val) {
        ++(root->count_left);
        insertNode(root->left, val);
    } else {
        insertNode(root->right, val);
    }
}

int getRank(TreeNode *root, int val)
{
    int result;
    TreeNode *ptr;
    
    result = 0;
    ptr = root;
    while (ptr != nullptr) {
        if (ptr->val > val) {
            ptr = ptr->left;
        } else if (ptr->val < val) {
            result += ptr->count_left + 1;
            ptr = ptr->right;
        } else {
            break;
        }
    }
    if (ptr != nullptr) {
        result += ptr->count_left;
        return result;
    } else {
        return -1;
    }
}

void clearTree(TreeNode *&root)
{
    if (root != nullptr) {
        clearTree(root->left);
        clearTree(root->right);
        delete root;
        root = nullptr;
    }
}

int main()
{
    int val;
    TreeNode *root;
    string s;
    
    root = nullptr;
    while (cin >> s) {
        if (s == "i") {
            cin >> val;
            insertNode(root, val);
        } else if (s == "r") {
            cin >> val;
            printf("rank = %d\n", getRank(root, val));
        } else if (s == "e") {
            break;
        }
    }
    clearTree(root);
    
    return 0;
}

?