专栏首页奔跑的蛙牛技术博客基于链表的无序查找

基于链表的无序查找

package com.snail.basic;


public class SequentialSearchST<Key, Value> {
    // 链表首结点
    private Node first;

    private class Node {
        // 链表结点定义
        Key key;
        Value val;
        Node next;

        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    public Value get(Key key) {
        // 查找给定的键,返回相连的值
        for (Node x = first; x != null; x = x.next)
            if (key.equals(x.key))
                return x.val;
        return null;
    }

    public void put(Key key, Value val) {
        // 查找给定的键,找到则更新其值,否则在表中新建结点
        for (Node x = first; x != null; x = x.next)
            if (key.equals(x.key)) {
                // 命中 更新
                x.val = val;
                return;
            }
        // 未命中新建结点
        first = new Node(key, val, first);
    }

}
package com.snail.basic;

/**
 * 二分查找基于有序数组
 * 
 * @param <Key> 有序排列的键
 * @param <Value> 键对应的值
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;
    public BinarySearchST(int capacity){
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }
    public int size(){
        return N;
    }
    public Value get(Key key){
        int i = rank(key);
        if(i<N&&keys[i].compareTo(key)==0)return vals[i];
        else return null;
        
    }
    public int rank(Key key){
        int lo = 0,hi =N-1;
        while (lo<=hi){
            int mid = lo + (hi-lo)/2;
            int cmp = key.compareTo(keys[mid]);
            if(cmp<0)hi=mid-1;
            else if(cmp>0)lo=mid+1;
            else return mid;
        }
        return lo;
    }
    public void put(Key key,Value val){
        int i = rank(key);
        if(i<N && keys[i].compareTo(key)==0){
            vals[i] = val;return;
        }
        for (int j = N; j > i; j--) {
            keys[j]= keys[j-1];
            vals[j] = vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于堆的优先队列

    用户2436820
  • Java图形程序设计

    所有的Swing组件必须由时间分派线程(EventQueue.invokeLater)配置

    用户2436820
  • 快速排序

    用户2436820
  • HDU 1874 畅通工程续 dijkstra+priority_queue

    某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行...

    ACM算法日常
  • WorkManager从入门到实践,有这一篇就够了

    上一次我们对Paging的应用进行了一次全面的分析,这一次我们来聊聊WorkManager。

    Rouse
  • Java.lang.OutOfMemoryError处理

    听着music睡
  • java基础:枚举(你木有见过的船新版本)

    枚举经常用来设计一些常量,比如一星期有7天,且只能有唯一的7天,所以枚举是在一定的范围取值,并且必须是枚举类型中的任意一个,而且只能有一个

    用户7649162
  • 揭秘无人车暗战:苹果投资滴滴后,Uber想联手特斯拉为何被拒?

    若朴 编译整理 量子位 报道 | 公众号 QbitAI 去年5月13日,滴滴宣布获得苹果公司10亿美元战略投资,苹果也由此进入滴滴董事会。一年后,这件事的涟漪浮...

    量子位
  • iOS - 关于 KVC 的一些总结

    我们可以使用setter方法为currentBalance属性赋值,这是直接的,但缺乏灵活性。

    师大小海腾
  • 上海交大黑客松NVIDIA智能小车项目比赛纪实 |一个人的武林,一群人的黑客松

    人生追求的,无非是心的平安喜乐,天下第一是孤独的路,需要抛下太多人和事,才能站上狭小的峰顶。福,共同创造,苦,一同承受,天下第一的念头再也没有出现在我心中。 ...

    GPUS Lady

扫码关注云+社区

领取腾讯云代金券