《算法零基础100讲》哈希表

57 阅读 0 评论 38 点赞

我是靠谱客的博主拉长苗条，最近开发中收集的这篇文章主要介绍《算法零基础100讲》哈希表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.剑指 Offer 03. 数组中重复的数字

/*找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字 */
class Solution {
    public int findRepeatNumber(int[] nums) {
        int [] arr = new int [nums.length];
        for(int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;//遍历数组中的每个数字
            if(arr[nums[i]] > 1) {
                return nums[i];//如果遍历的数字重复（>1）返回这个重复的数字
            }
        }
        return -1;
    }
}

2.剑指 Offer II 076. 数组中的第 k 大的数字

/*
1.给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
2.请注意，你需要找的是数组排序后的第k个最大的元素，而不是第 k 个不同的元素*/
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

705. 设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。实现 MyHashSet 类：
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

class MyHashSet {
    boolean[] set = new boolean[1000001];//直接设置boolean的下标为key值
    public MyHashSet() {
    }
    
    public void add(int key) {
        set[key] = true;
    }
    
    public void remove(int key) {
        set[key] = false;
    }
    
    public boolean contains(int key) {
        return set[key] == true;
    }
}
 /*不使用任何内建的哈希表库设计一个哈希集合（HashSet）。实现 MyHashSet 类：
    void add(key) 向哈希集合中插入值 key 。
    bool contains(key) 返回哈希集合中是否存在这个值 key 。
    void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
 */