LeetCode 查找表专题 3：set 和 map 不同底层实现的区别

set 和 map 不同的底层实现，影响了算法的实现效率。C++ 中的 Set 和 Map 的 默认实现就是平衡二叉树，即二分搜索树。

下面分别是针对前两节问题的解答。
（1）第4-1节的问题

（2）第4-2节的问题

unorder_map 和 unorder_set 的经典的底层实现是哈希表。
在 Java 中，默认就是 hash 的实现，hash 表能够实现高效地查找，但是hash 表有一个很严重的问题：缺失了数据的顺序性。
但是二分搜索树，就可以保持数据的顺序性。数据的顺序性能够帮助我们完成：1、数据集中元素的最大值和最小值；

2、某个元素的前驱和后继；
3、某个元素的 floor 和 ceil；
4、某个元素的排位（元素排在第几名）；
5、选择某个排位的元素（select，第几名的元素是哪个？）

对于 hash 表来说，优点是查找， hash 表不能解决上面“数据的顺序性”部分说的 5 个问题。

对于上一节的问题：
时间复杂度是：O(nlogn)，这里的时间复杂度是如何分析出来的？
空间复杂度是：O(logn)

经典的实现：哈希表，哈希表的一个缺点是失去了数据的顺序性。
例：

对于上一节的问题：
时间复杂度是：O(nlogn)，这里的时间复杂度是如何分析出来的？
空间复杂度是：O(logn)

经典的实现：哈希表，哈希表的一个缺点是失去了数据的顺序性。

练习1：LeetCode 第 242 题：有效的字母异位词

传送门：英文网址：242. Valid Anagram ，中文网址：242. 有效的字母异位词 。

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

Java 代码1：把两个字符串都转换成字符数组以后，进行排序，然后逐位进行比较。

public class Solution {
    public boolean isAnagram(String s, String t) {
        boolean isAnagram = true;
        if (s.length() != t.length()) {
            isAnagram = false;
        } else {
            char[] sArray = s.toCharArray();
            Arrays.sort(sArray);
            char[] tArray = t.toCharArray();
            Arrays.sort(tArray);
            for (int i = 0; i < sArray.length; i++) {
                if (sArray[i] != tArray[i]) {
                    isAnagram = false;
                    break;
                }
            }
        }
        return isAnagram;
    }
}

Java 代码2：放入一个 Map 中，只要后面有一个元素不出现在 Map 中，就退出，最后应该使得这个 Map 里所有元素的 value 值都为 0。

public class Solution2 {
    public boolean isAnagram(String s, String t) {
        boolean isAnagram = true;
        if (s.length() != t.length()) {
            isAnagram = false;
        } else {
            char[] sArray = s.toCharArray();
            Map<Character, Integer> map1 = new HashMap<>();
            for (char c : sArray) {
                if (map1.containsKey(c)) {
                    map1.put(c, map1.get(c) + 1);
                } else {
                    map1.put(c, 1);
                }

            }

            char[] tArray = t.toCharArray();
            for (char c : tArray) {
                if (map1.containsKey(c) && map1.get(c) >= 1) {
                    map1.put(c, map1.get(c) - 1);
                } else {
                    isAnagram = false;
                    break;
                }
            }

        }
        return isAnagram;
    }
}

Python 代码：

from collections import Counter
class Solution:
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        c1 = Counter(s)
        c2 = Counter(t)
        if (c1 == c2):
            return True
        return False

练习2：LeetCode 第 202 题：快乐数

传送门：202. 快乐数。

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例:

输入: 19
输出: true
解释: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路：用散列表判断是否会遇到重复的数，遇到重复的数，就表示会死循环。

Python 代码：

class Solution:
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        # 得到一个数的每个数位
        s = set()
        while True:
            square_sum = 0
            while n != 0:
                mod = n % 10
                square_sum += mod ** 2
                n = n // 10
            if square_sum == 1:
                return True
            if square_sum in s:
                return False
            else:
                s.add(square_sum)
                n = square_sum


if __name__ == '__main__':
    n = 19
    s = Solution()

    result = s.isHappy(n)
    print(result)

练习3：LeetCode 第 290 题：单词模式

传送门：英文网址：290. Word Pattern ，中文网址：290. 单词模式 。

给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。

示例1:

输入: pattern = "abba", str = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"
输出: false

说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

分析：建立双向单映射，即不同的字母不能映射到相同的单词。这里有一个小小的坑，就是当测试用例是： String pattern = "abba";String str = "dog dog dog dog"; 的时候，我们须要判断出结果是 false。

Java 代码：

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        boolean wordPattern = false;
        int patternLength = pattern.length();
        String[] strArray = str.split(" ");
        if (patternLength == strArray.length) {

            Map<Character, String> map1 = new HashMap<>();
            Set<String> uniqueValue = new HashSet<>();
            char[] patternArray = pattern.toCharArray();
            for (int i = 0; i < patternLength; i++) {
                if (map1.containsKey(patternArray[i])) {
                    if (!map1.get(patternArray[i]).equals(strArray[i])) {
                        return wordPattern;
                    }
                } else {
                    if (uniqueValue.contains(strArray[i])) {
                        return wordPattern;
                    }
                    uniqueValue.add(strArray[i]);
                    map1.put(patternArray[i], strArray[i]);
                }
            }
            wordPattern = true;
        }
        return wordPattern;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String pattern = "abba";
        String str = "dog dog dog dog";
        boolean wordPattern = solution.wordPattern(pattern, str);
        System.out.println(wordPattern);
    }
}

练习4：LeetCode 第 205 题：同构字符串

传送门：英文网址：205. Isomorphic Strings ，中文网址：205. 同构字符串 。

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

说明:
你可以假设 s 和 t 具有相同的长度。

思路：建立映射关系的时候，要检查是不是两个 key 对应到同一个 value 上了。

• 使用 Hash 表进行映射关系的建立，和检查 value 是否重复。
• 对于字符映射的问题而言，Hash 表还可以使用字符数组得到同样的效果。

Java 代码：

public class Solution4 {

    public boolean isIsomorphic(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if (slen != tlen) {
            return false;
        }
        Character[] map = new Character[256];
        boolean[] set = new boolean[256];
        for (int i = 0; i < slen; i++) {
            char key = s.charAt(i);
            char value = t.charAt(i);
            if (map[key] == null) {
                // 建立映射关系
                if (set[value]) {
                    return false;
                }
                map[key] = value;
                set[value] = true;
            } else {
                if (map[key] != value) {
                    return false;
                }
            }
        }
        return true;
    }
}

练习5：LeetCode 第 451 题：根据字符出现频率排序

传送门：451. 根据字符出现频率排序。

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

分析：题目的要求是很简单的。其实就是要我们“将字符串里的字符按照出现的频率降序排列”，为此，我们要做一个计数器，然后给 sort 函数一个排序规则就可以了。这是我们最容易想到的。

思路1：指定排序规则

Python 代码：

class Solution:
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """

        d = dict()
        # 词频统计
        for char in s:
            d[char] = d.setdefault(char, 0) + 1
        # 按照词频降序排序
        sorted_item = sorted(d.items(), key=lambda x: x[1], reverse=True)
        result = ''
        for key, count in sorted_item:
            result += key * count
        return result

思路2：我们又注意到，其实我们每次只关心频次最大的那个数，不妨借助最大堆，即使用优先队列，Python 中的优先队列可以传入 tuple。

Python 代码：

class Solution:
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """

        l = len(s)
        if l <= 1:
            return s

        d = dict()
        for alpha in s:
            d[alpha] = d.setdefault(alpha, 0) + 1
        # print(d.items())

        import heapq
        h = []
        for alpha, counter in d.items():
            heapq.heappush(h, (-counter, alpha))
        res = ''

        dl = len(d.items())

        for _ in range(dl):
            counter, alpha = heapq.heappop(h)
            res += alpha * (-counter)
        return res

思路3：有很多重复键值的排序任务，可以使用三路快排。

其实，这道问题做到这里感觉已经差不多了。但注意到这道题的特殊性，待排序的字符串的字符是有限的：26 个小写英文字母 + 26 个大写英文字母，再加上一些特殊字符，在字符串很长的时候，就会有大量的重复元素。而有大量重复元素的排序任务恰恰好是三路快速排序擅长处理的问题。我们注意到这一点，就可以手动编写三路快排，当然我觉得如果在面试中，先写上面的写法是肯定没有问题的，也是应该最先想到的。三路快排的写法并没有改变这个问题求解的本质。

Java 代码：

class Solution {
    private Random random = new Random();

    public String frequencySort(String s) {
        char[] chars = s.toCharArray();
        // 记录每个字符出现的频次, 数字下标为字符ASCII码, LeetCode这题的测试用例128已经够用了
        int[] freq = new int[128];
        // 遍历字符数组, 计算每个字符出现的频次, 这一步时间复杂度O(n)
        for (int i = s.length() - 1; i >= 0; i--) {
            freq[chars[i]]++;
        }

        // 对chars数组进行三路快排, 设定频次越高的字符值越大,频次相等时再按照字符ASCII码进行比较
        // 排序这一步时间复杂度为O(nlogn), 所以整个算法的时间复杂度是O(nlogn)
        quicksort3Ways(chars, 0, s.length() - 1, freq);
        // 排序完成之后
        return  new String(chars);
    }

    /**
     * 三路快排, 递归算法, 对chars数组的[l...r]前闭后闭区间进行排序
     * @param chars : 要排序的字符数组
     * @param l : 数组左边界
     * @param r : 数组右边界
     * @param freq : 字符出现频次, 设定字符大小与频次高低一致
     */
    private void quicksort3Ways(char[] chars, int l, int r, int[] freq){
        // 递归终止条件,只有一个元素时默认数组是有序的
        if (r - l < 1) {
            return;
        }

        // 选取标定点, 随机选取, 避免数组本身是有序的导致快排性能下降
        int pivotIndex = random.nextInt(r - l + 1) + l;
        swap(chars, l, pivotIndex);
        char pivot = chars[l];
        // 设定chars[l+1...left] < pivot, chars[left + 1, i) == pivot, chars[right, r] < pivot
        int left = l, right = r + 1, i = l + 1;
        while(i < right){
            // 大于pivot的元素
            if (compare(chars[i], pivot, freq) > 0) {
                swap(chars, left + 1, i);
                left++;
                i++;
            // 小于pivot的元素
            } else if (compare(chars[i], pivot, freq) < 0) {
                swap(chars, right - 1, i);
                // right - 1的元素还没有遍历, 所以这里只需要right--, 并不用i++
                right--;
            } else {
                i++;
            }
            
        }

        // chars[l]==pivot, 所以最后需要将l与left交换位置
        swap(chars, l , left);
        // 递归对小于pivot的元素再进行排序
        quicksort3Ways(chars, l, left, freq);
        // 递归对大于pivot的元素再进行排序
        quicksort3Ways(chars, right, r, freq);
    }

    public int compare(char c1, char c2, int[] freq) {
        if (freq[c1] == freq[c2]){
            return c1 - c2;
        }
        return freq[c1] - freq[c2];
    }

    /**
     * 对数组chars数组中index1,index2位置的两个元素进行交换
     * @param chars
     * @param index1
     * @param index2
     */
    private void swap(char[] chars, int index1, int index2){
        char temp = chars[index1];
        chars[index1] = chars[index2];
        chars[index2] = temp;
    }

    public static void main(String[] args) {
        new Solution().frequencySort("cccaaa");
    }

}

（本节完）