菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
1626
0

14-1 哈希表基础 / Leetcode first uniq char

原创
05/13 14:22
阅读数 1828

知识点:
1 将 a-z 字幕的 ascii 码出现次数映射到 0-25 的数组中 , 哈希函数 f(char)=char-'a' O(1) , 键转换为索引
2 26 个字幕和 1-30 学号这样的哈希函数很容易能找到一一对应的索引 , 但是身份证,字符串,浮点数,日期却不能 , 可能是多对一 , 因而产生哈希冲突
3 哈希表的设计思想: 空间换时间 , 假如1101819851216666 的身份证 , 可以开辟无限大的 99999999999999 的数组,则可以用 O(1)的时间执行任意操作 , 假如只有 1 的空间, 则只能类似链表(线性表) , O(n)的时间操作

func firstUniqChar(s string) int {
    /*
    make a arr , map 0-25 as a-z
     */
    arr:=[26]int{}

    for _,v:=range s {
            arr[v-'a']++

    }

    for k,v:=range s {
        if arr[v-'a']==1 {
            return k
        }
    }
    return -1

}

发表评论

0/200
1626 点赞
0 评论
收藏
为你推荐 换一批