JZTXT

LeetCode —— 哈希表

发布时间 2023-07-12 21:19:50作者: archaique

128. 最长连续序列

不要求在位置数组中是连续的

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

两种最朴素的解法之一：

  1. 先排序，从前往后找最长连续上升序列即可。该思路简单有效，但是复杂度已经至少有 O(nlogn)。实现起来也比较简单，在此不讨论该解法。
  2. 遍历数组中的每个元素num，然后以num为起点，每次+1向后遍历num+1,num+2,num+3...，判断这些元素是否存在于数组中。假设找到的最大的连续存在的元素为num+x，那么这个连续序列的长度即为x+1。最后将每个num所开始序列长度取个最大值即可。

解题思路1：哈希集合
上面的代码不用想，是肯定超时的。它的最坏时间复杂度已经达到了 O(n^3)
我们需要优化代码。优化的点主要有两个：

  1. 判断num+1，num+2，num+3...是否在数组中。上面的代码是用直接遍历的方式去查找的，时间复杂度为 O(n) 。我们可以改为哈希表查找，时间复杂度为 O(1)
  2. 遍历数组中每个元素num。逐一遍历每个元素会产生很多冗余工作，实际上我们无需一次针对每个元素num去判断num+1，num+2，num+3...是否在数组中。如果num-1已经在数组中的话，那么num-1肯定会进行相应的+1遍历，然后遍历到num，而且从num-1开始的+1遍历必定比从num开始的+1遍历得到的序列长度更长。因此，我们便可将在一个连续序列中的元素进行删减，让其只在最小的元素才开始+1遍历。比如，现有元素[1,2,4,3,5]，当2,3,4,5发现均有比自己小1的元素存在，那么它们就不会开始+1遍历，而1是连续序列中最小的元素，没有比自己小1的元素存在，所以会开始+1遍历。通过上述方式便可将时间复杂度优化至O(n)。

参考题解： https://leetcode.cn/problems/longest-consecutive-sequence/solution/xiao-bai-lang-ha-xi-ji-he-ha-xi-biao-don-j5a2/

class Solution {

    //哈希表实现。哈希表的 插入、删除、查找的时间复杂度近似为 O(1)
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet();
        // 每个加到哈希表里（去重）
        for (int i=0;i<nums.length;i++) {
            set.add(nums[i]);
        }

        int ans = 1;
        for (int num:set) {
            int cur = num;
            // 如果 num-1 存在，那么 num 就不用搜索了，搜索 num-1 的时候一直往后 +1 搜索会把 num 包括进去
            // 当 num-1 不存在，才开始往后搜索
            if (!set.contains(num-1)) {
                // 只有当num-1不存在时，才开始向后遍历num+1，num+2，num+3......
                while (set.contains(cur+1)) {
                    cur++;
                }
                // [num, cur] 是连续的区间
                ans = Math.max(ans, cur-num+1);
            }
        }
        return ans;
    }


    // 这样复杂度取决于排序的复杂度
    public int longestConsecutive2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 排序
        Arrays.sort(nums);
        int longestLen = 1;
        int curLen = 1;
        for (int i=0;i<nums.length;i++) {
            if (i > 0) {
                //  0 1 1 1 2 这种，前面重复的1都跳过跳过
                if (nums[i] == nums[i-1]) {
                    continue;
                }
                // 0 1 1 1 2 这种，到 2 的时候，不能和前一个 1 比较，要一直跳到第一个 1 去比较
                int lastDiffIndex = i-1;
                while (lastDiffIndex > 0 && nums[lastDiffIndex] == nums[lastDiffIndex-1]) {
                    lastDiffIndex-=1;
                }
                // 已排序，与前一个的差值为 1 则说明是连续的
                if (nums[i] - nums[lastDiffIndex] == 1) {
                    longestLen = Math.max(longestLen, curLen+=1);
                }
                else {
                    // 不连续了，curLen 重新开始计算
                    curLen = 1;
                }
            }
        }
        return longestLen;
    }
}

 

 

49. 字母异位词分组

字母异位的词排序之后都是一样的

所以对每个字符串先排序

排序后的字符串作为 HashMap 的 key

而 value 则是字母异位词的 List

注意对字符串排序的方法是

char[] orderStrArr = str.toCharArray();
Arrays.sort(orderStrArr);
String orderStr = String.valueOf(orderStrArr);
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> orderStr2StrListMap = new HashMap();
        for (String str : strs) {
            char[] orderStrArr = str.toCharArray();
            Arrays.sort(orderStrArr);
            String orderStr = String.valueOf(orderStrArr);
            List<String> strList = orderStr2StrListMap.get(orderStr);
            if (strList == null) {
                strList = new ArrayList();
                orderStr2StrListMap.put(orderStr, strList);
            }
            strList.add(str);
        } 

        List<List<String>> res = new ArrayList();
        for(Map.Entry<String, List<String>> entry : orderStr2StrListMap.entrySet()) {
            res.add(entry.getValue());
        }
        return res;
    }
}