less = mostRightLessNodeInTree(key);SkipListNode next = less.nextNodes.get(0);return next != null && next.isKeyEqual(key);}// 新增、改valuepublic void put(K key, V value) {if (key == null) {return;}// 0层上，最右一个，< key 的Node -> >keySkipListNode less = mostRightLessNodeInTree(key);SkipListNode find = less.nextNodes.get(0);if (find != null && find.isKeyEqual(key)) {find.val = value;} else { // find == null879size++;int newNodeLevel = 0;while (Math.random() < PROBABILITY) {newNodeLevel++;}// newNodeLevelwhile (newNodeLevel > maxLevel) {head.nextNodes.add(null);maxLevel++;}SkipListNode newNode = new SkipListNode(key, value);for (int i = 0; i <= newNodeLevel; i++) {newNode.nextNodes.add(null);}int level = maxLevel;SkipListNode pre = head;while (level >= 0) {// level 层中，找到最右的 < key 的节点pre = mostRightLessNodeInLevel(key, pre, level);if (level <= newNodeLevel) {newNode.nextNodes.set(level, pre.nextNodes.get(level));pre.nextNodes.set(level, newNode);}level--;}}}public V get(K key) {if (key == null) {return null;}SkipListNode less = mostRightLessNodeInTree(key);SkipListNode next = less.nextNodes.get(0);return next != null && next.isKeyEqual(key) ? next.val : null;}public void remove(K key) {if (containsKey(key)) {size--;int level = maxLevel;SkipListNode pre = head;while (level >= 0) {pre = mostRightLessNodeInLevel(key, pre, level);SkipListNode next = pre.nextNodes.get(level);// 1）在这一层中，pre下一个就是key// 2）在这一层中，pre的下一个key是>要删除keyif (next != null && next.isKeyEqual(key)) {// free delete node memory -> C++// level : pre -> next(key) -> ...pre.nextNodes.set(level, next.nextNodes.get(level));}// 在level层只有一个节点了，就是默认节点headif (level != 0 && pre == head && pre.nextNodes.get(level) == null) {head.nextNodes.remove(level);maxLevel--;}level--;}}}public K firstKey() {return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;}public K lastKey() {int level = maxLevel;SkipListNode cur = head;while (level >= 0) {SkipListNode next = cur.nextNodes.get(level);while (next != null) {cur = next;next = cur.nextNodes.get(level);}level--;}return cur.key;}public K ceilingKey(K key) {if (key == null) {return null;}SkipListNode less = mostRightLessNodeInTree(key);SkipListNode next = less.nextNodes.get(0);return next != null ? next.key : null;}public K floorKey(K key) {if (key == null) {return null;}SkipListNode less = mostRightLessNodeInTree(key);SkipListNode next = less.nextNodes.get(0);return next != null && next.isKeyEqual(key) ? next.key : less.key;}public int size() {return size;}}
有序表题目
题目一
给定一个数组arr，和两个整数a和b（a
