【LeetCode】五、哈希表相关：统计重复元素 + 找不同

1、哈希表结构

又叫散列表，存键值对，将key用哈希函数转为数组下标索引

当两个不同的key经过哈希函数得到相同的结果i，即哈希冲突了

此时 i 位置就要存两个值，因此，链表出现，如下图中数组下标2的位置：

时间复杂度：根据key找value，时间复杂度为O(1)，但如果有哈希冲突，则时间复杂度为O(k)，k为冲突位置链表元素的个数

2、Java中的哈希表

下面这种用数组表示哈希表的结构，是key为下标索引，value为数组元素的值。重点关注HashMap就行：

3、leetcode217：统计重复元素

单论这题要return的结果，其实不借助数据结构，直接for循环遍历，里面再嵌套遍历一次，出现一个相等就直接return true就实现了。下面的解法，重点在有重复元素 + 每个重复元素分别重复了几次

哈希表的一个常见用途就是统计某个元素或字符出现的次数

统计思路：遍历数组，如果数组的元素e不在哈希表的key的集合中，则put(e, 1)，反之，若在，则get这个key的value，并将其value更新为value+1。 再说这道题，要结果就遍历下HashMap，如果有value大于1的，则return true

public class P217 {

    public static boolean stats(int[] array) {
        if (null == array || array.length == 0) {
            return false;
        }
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int e : array) {
            if (!hashMap.containsKey(e)) {
                hashMap.put(e, 1);
            } else {
                int count = hashMap.get(e);
                hashMap.put(e, count + 1);
            }
        }
        // 统计完毕了，这里完成下题目的return值
        for (Integer value : hashMap.values()) {
            if (value > 1){
                return true;
            }
        }
        return false;
    }
}

测试：

public class P217 {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 1, 1};
        System.out.println(stats(array));
    }
}

效果：

4、leetcode389：找不同

用数组实现，还是哈希表的思路，将每个字母根据ASCII码转为数组下标，数组的值则存其出现的次数。两个注意点：

• a对应的ASCII码为97，没必要存97的位置，存0，b就存98 - a = 98 - 97 = 1
• 两个字符串，没必要对应两个数组，用一个，s字符串中的每个字母出现一次就减1，t字符串则加1，如此，最后数量不为1的位置，即为随机添加的那个字母

实现：

public class P389 {

    public static String findDifference(String t, String s) {
        if (s.length() == 0) {
            return t;
        }
        // 初始化一个空int数组，长度为26，因为最多26个字母
        int[] array = new int[26];
        char[] tArr = t.toCharArray();
        char[] sArr = s.toCharArray();
        for (char i : tArr) {
            // char类型转int即为其ASCII码
            array[(int)i - 97] = array[(int)i - 97] + 1;
        }
        for (char j : sArr) {
            array[(int)j - 97] = array[(int)j - 97] - 1;
        }

        for (int i = 0; i < array.length; i++) {
            if (array[i] > 0) {
                // 找到多余的字母以后，用其索引下标+97转回字符
                return (char)(i + 97) + "";
            }
        }
        return "";
    }
}

测试：

public class P389 {
    public static void main(String[] args) {
        String s = "abcd";
        String t = "abcda";
        System.out.println(findDifference(t, s));
    }
}

本质还是key-value的哈希表思想，不过是key的特殊性，用数组直接实现了。特别注意这里加一减一的思想，而不是用两个哈希表分别统计。

5、leetcode496：下一个更大元素

之前用两个栈解决过这题，还可用栈 + 哈希表解决，更加清晰。思路：直接计算num2中每个元素在num2中下一个更大的值，并存入哈希表，key为num2的每个元素，value为该元素的下一个更大的值。如此，遍历num1，直接从哈希表get，就可得到其下一个更大的值

计算num2中每个元素在num2中下一个更大的值，可借助栈，遍历num2，入栈，当即将入栈的元素a 大于 栈顶元素b的时候，即说明a是b的下一个更大的元素，存入map

public class P496Two {

    public static int[] findMore(int[] num1, int[] num2) {
        if (num1 == null || num2 == null || num1.length == 0 || num2.length == 0){
            return null;
        }
        //结果集
        int[] result = new int[num1.length];
        //栈和哈希表
        Stack<Integer> stack = new Stack<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        // 栈不空，且即将入栈的元素大于栈顶元素的时候
        for (int num : num2) {
            while (stack.size() != 0 && num > stack.peek()) {
                // 即将入栈的元素就是栈顶元素的"下一个更大值"，存入map
                Integer key = stack.pop();
                map.put(key, num);
            }
            stack.push(num);
        }

        // 栈里还有元素的话，说明后面没有比它更大的了，统统弹栈，更大的值赋-1
        while (stack.size() != 0) {
            map.put(stack.pop(), -1);
        }

        // 到此，map中存了num2里每个元素的"下一个更大值"，返回num1的
        for (int i = 0; i < num1.length; i++) {
            result[i] = map.get(num1[i]);
        }
        return result;

    }
}

测试下：

public class P496Two {

    public static void main(String[] args) {
        int[] num1 = {8, 1, 2};
        int[] num2 = {2, 1, 0, 8, 7, 6, 5};
        for (int i : findMore(num1, num2)) {
            System.out.print(i + " ");
        }
    }
}