听寒's Blog

const double PFACTOR = 0.25;
const int MAX_LEVEL = 32;
class Skiplist {
    struct Node {
        int val;
        vector<Node*> forward;
        Node(int _val, int level): val(_val), forward(level, nullptr) {
        }
    };
    random_device rd;
    mt19937 gen{rd()};
    uniform_real_distribution<double> dis{0, 1};
public:
    Node* head;
    int level;
    Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        level = 0;
    }
    bool search(int target) {
        Node *cur=this->head;
        for(int i=level-1; i>=0; i--) {
            while(cur->forward[i] && cur->forward[i]->val < target) {
                cur = cur->forward[i];
            }
        }
        cur = cur->forward[0];
        return cur && cur->val == target;
    }
    void add(int num) {
        int lv=randomLv();
        level=max(level, lv);
        array<Node*, MAX_LEVEL> shouldupdate;
        Node *cur=this->head;
        for(int i=level-1; i>=0; i--) { // 找到各层要更新的结点
            while(cur->forward[i] && cur->forward[i]->val < num) {
                cur = cur->forward[i];
            }
            shouldupdate[i] = cur; // 虽然全部记录了但是并不是全部都用了
        }
        Node *newNode=new Node(num, lv);
        for(int i=0; i<lv; i++) { // 只有前Lv层（结点所在那些层级）的前序节点才会被更新
            newNode->forward[i] = shouldupdate[i]->forward[i];
            shouldupdate[i]->forward[i] = newNode;
        }
         return;
    }
    
    bool erase(int num) {
        array<Node*, MAX_LEVEL> shouldupdate;
        Node *cur=this->head;
        for(int i=level-1; i>=0; i--) {
            while(cur->forward[i] && cur->forward[i]->val < num) {
                cur = cur->forward[i];
            }
            shouldupdate[i] = cur;
        }
        cur = cur->forward[0]; // 最底层再推进一次应该就是要删除的元素
        if (!(cur && cur->val == num)) return false; // 说明当前skiplist不存在该元素
        // 从最底0层开始更新前序节点，直到没有这个元素的层数上
        for(int i=0; i<level && shouldupdate[i]->forward[i]==cur; i++) {
            shouldupdate[i]->forward[i] = cur->forward[i];
        }
        delete cur; // 删除节点本身
        while(level>1 && !head->forward[level-1]) { // 如果删除节点使得顶上几层变为了空，我们需要删除顶上这些层
            level--;
        }
        return true;
    }
private:
    int randomLv() {
        int lv=1;
        while(dis(gen)<PFACTOR && lv<MAX_LEVEL) lv++;
        return lv;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    // 所有可能性：left: [0, n]  right: [-1, n-1] mid: [0, n-1]
    if (left >= nums.length || nums[left] != target) 
        return -1;
    return left;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况，见下图
    if (right < 0 || nums[right] != target)
        return -1;
    return right; // 若要求upper_bound（下一个不等于target的位置）则是return left;
}