0%

LeetCode Hash Table

Posted on Edited on In
Symbols count in article: 5.9k

合理安排时间，等于节约时间。——培根

LeetCode哈希表、相关题目，其解决思路和具体代码。以及有关java语言哈希表的解析。

242. Valid Anagram(有效的字母异位词)(Easy)

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

解：这道题可以直接把传入的两个字符串转换成字符数组，按照字典序排序后比较是否相等。这种方法不需要用到哈希表，但是类库自带的快排整体速度不如哈希表(这道题实际上使用到哈希表的思想，我们自己定义一个哈希映射)的查询速度快。

方法一：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        Arrays.sort(s1);
        Arrays.sort(t1);
        return Arrays.equals(s1,t1);
    }
}

方法二：使用哈希映射思想，定义一个我们自己的哈希表，遍历s和t，每次把s中遍历到的字母的ASICC码计算并且加起来，再减去t中对应的值。遍历一遍下来，如果有一个字母的对应的出现次数不为0，则整个传入数据不为字母异位词。此方法中new了一个大小为26的数组，其中每一个元素代表一个字母的出现次数，所以最后只要有一个不为0，输入就不为字母异位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        
        int[] count = new int[26];
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        
        for(int i = 0 ; i < s1.length; i++) {
            count[s1[i] - 'a']++;
            count[t1[i] - 'a']--;
        }
        
        for(int i = 0; i < 26; i++) {
            if(count[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

注意，如果不先将s和t 进行toCharArray转换，而直接用charAt()判断位置然后进行哈希映射，整体执行效率会很慢。上面的用时可以击败90%以上，但是下面这段代码一般只能击败60%，试验了多次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        
        int[] count = new int[26];
        
        for(int i = 0 ; i < s.length() ;i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        
        for(int counter : count) {
            if(counter != 0) {
                return false;
            }
        }
        return true;
    }
}

49. Group Anagram(字母异位词分组)(Mid)

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

解：使用排序解决判断是否为异位词的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs.length == 0 || strs == null) return new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<>();
        for(String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String keyStr = String.valueOf(ca);
            if(!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<>());
            map.get(keyStr).add(s);
        }
        return new ArrayList<List<String>> (map.values());
    }
}

1. Two Sum(两数之和)(Easy)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解：保持数组中的每个元素与其索引相互对应的最好方式是什么？当然是基于数组的哈希表。利用哈希表先把内容存储起来，这样一来查找的过程只需要O(1)了。

这个map中，key是nums元素的值，value是该元素的下标。因为要找到a+b = target,所以 a = target - b，所以查找 target-a 在不在数组里面即可。

注意

  1. 这里是把元素当做key，该元素的位置当做value。
  2. 虽然看起来 map.put(nums[i], i) 这句放在循环体里的前面和后面都可以，但是其实是不能放在前面的，否则如果某个元素的值是target的二分之一，先把它添加进map之后再比较，会直接比较到它自己。换句话说，必须先比较，再put进map。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                result[0] = i;
                result[1] = map.get(target - nums[i]);
                break;
            }
            // 注意这里put不能放在判断前面，必须先比较再放入。否则如果某个元素是target的一半，先添加再比较的话，会比较到它自己。
            map.put(nums[i],i);
        }
        return result;
    }
}

347. Top K Frequent Elements (前K个高频元素)(Mid)

Given a non-empty array of integers, return the k\ most frequent elements.

Example 1:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

解：具体解法可以参考这篇文章

这里有好用的两种方法，都用到了HashMap。

方法一**：堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new LinkedList<>();
        if(nums.length == 0 || nums == null || k == 0) return result;

        // 第一个Integer为元素值，第二个为对应的频次
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int num:nums) {
            if(map.containsKey(num))
                map.put(num, map.get(num)+1);
            else
                map.put(num, 1);
        }
        
        // 构建小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a,b) -> map.get(a)-map.get(b)
        );
        
        for(int key : map.keySet()) {
            // 起步阶段，还没有存满k个元素
            if(heap.size() < k)
                heap.add(key);
            // 如果新遍历的元素的频次大于优先队列中频次最小的元素，则要把
            //最小的元素进行替换
            else {
                if(map.get(key) > map.get(heap.peek())) {
                    heap.poll();
                    heap.add(key);
                }
            }
        }
        while(!heap.isEmpty())
            result.add(heap.poll());
        return result;
    }
}
  • 时间复杂度：O(nlogk)，注意不是O(nlogn)，n是数组长度，首先过一遍数组并且统计，这个操作时间复杂度为O(n)，然后遍历用于存储元素频率的map，如果元素的频率大于最小堆中顶部的元素，则将顶部的元素删除并将该元素加入堆中，这里维护堆的数目是 kk，所以这一系列操作的时间复杂度是 O(nlogk) 的；因此，总的时间复杂度是 O(nlog⁡k)。
  • 空间复杂度：O(n)，最坏情况下（每个元素都不同），map 需要存储 n 个键值对，优先队列需要存储 k 个元素，因此，空间复杂度是 O(n)。

方法二：桶排序

首先依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//基于桶排序求解「前 K 个高频元素」
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList();
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
               map.put(num, map.get(num) + 1);
             } else {
                map.put(num, 1);
             }
        }
        
        //桶排序
        //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
        List<Integer>[] list = new List[nums.length+1];
        for(int key : map.keySet()){
            // 获取出现的次数作为下标
            int i = map.get(key);
            if(list[i] == null){
               list[i] = new ArrayList();
            } 
            list[i].add(key);
        }
        
        // 倒序遍历数组获取出现顺序从大到小的排列
        for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
            if(list[i] == null) continue;
            res.addAll(list[i]);
        }
        return res;
    }
}
  • 时间复杂度：O(n)，n 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；桶的数量为 n + 1，所以桶排序的时间复杂度为 O(n)O(n)；因此，总的时间复杂度是 O(n)。
  • 空间复杂度：O(n)