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

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

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

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 大的数字

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;
    }
}