Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2646901
  • 博文数量: 104
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 955
  • 用 户 组: 普通用户
  • 注册时间: 2019-10-28 13:40
文章分类

全部博文(104)

文章存档

2021年(32)

2020年(50)

2019年(22)

我的朋友

分类: Python/Ruby

2021-03-23 17:21:01

Python实现

class Skiplist:

    def __init__(self):

        self.head = Node()  # dummy head

    def search(self, target: int) -> bool:

        node = self.head

        while node:

            while node.right and node.right.val < target:

                node = node.right

            if node.right and node.right.val == target:

                return True

            node = node.down  # 这一层没有,往下一层

        return False

    def add(self, num: int) -> None:

        nodes = []

        node = self.head

        while node:

            # Move to the right in the current level

            while node.right and node.right.val < num:

                node = node.right

            nodes.append(node)

            # Move to the next level

            node = node.down

        insert = True

        down = None

        while insert and nodes:

            node = nodes.pop()

            node.right = Node(num, node.right, down)

            down = node.right

            insert = (random.getrandbits(1) == 0)

        # Create a new level with a dummy head

        # right = None

        # down = current head

        if insert:

            self.head = Node(-1, None, self.head)

    def erase(self, num: int) -> bool:

        node = self.head

        found = False

        while node:

            # Move to the right in the current level

            while node.right and node.right.val < num:

                node = node.right

            # Find the target node

            if node.right and node.right.val == num:

                # Delete by skipping

                node.right = node.right.right

                found = True

            # Move to the next level

            node = node.down

        return found

class Node:

    def __init__(self, val=-1, right=None, down=None):

        self.val = val

        self.right = right

        self.down = down

# Your Skiplist object will be instantiated and called as such:

# obj = Skiplist()

# param_1 = obj.search(target)

# obj.add(num)

# param_3 = obj.erase(num)

Java实现

class Skiplist {

    class Node {

        int val;

        Node right;

        Node down;

        Node(){

            this(-1, null, null);

        }

        Node(int val, Node right, Node down) {

            this.val = val;

            this.right = right;

            this.down = down;

        }

    }

    Node head;

    public Skiplist() {

        this.head = new Node();

    }

    public boolean search(int target) {

        Node node = head;

        while(node != null) {

            while(node.right != null && node.right.val < target)

                node = node.right;

            if(node.right != null && node.right.val == target)

                return true;

            node = node.down;

        }

        return false;

    }

    public void add(int num) {

        Node node = head;

        LinkedList nodes = new LinkedList<>();

        while(node != null) {

            while(node.right != null && node.right.val < num) {

                node = node.right;

            }

            nodes.add(node);

            node = node.down;

        }

        // 向上回溯,根据概率判断是否新增节点

        boolean isInsert = true;    // 最下面一层 100% 要新增

        double c = 1.0;

        Node down = null;           // 记录一下下面一层的down指针

        while 货币符号(!nodes.isEmpty() && isInsert) {

            Node cur = nodes.removeLast();

            cur.right = new Node(num, cur.right, down);

            down = cur.right;

            isInsert = count(c++);

        }

        if(isInsert)

            this.head = new Node(-1, null, head);

    }

    public boolean erase(int num) {

        Node node = head;

        boolean res = false;

        while(node != null) {

            while(node.right != null && node.right.val < num) {

                node = node.right;

            }

            if(node.right != null && node.right.val == num) {

                res = true;

                node.right = node.right.right;

            }

            node = node.down;

        }

        return res;

    }

// 计算概率

    static boolean count(double i) {

        double x = new Random().nextDouble();

        double y = 1 / Math.pow(2, i);

        return x <= y;

    }

}

阅读(3862) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~