LeetCode之哈希表

发表于 | | 热度: ℃
字数统计: 5.1k 字 | 阅读时长 ≈ 23 分钟

705. 设计哈希集合

难度:容易

要求

  • 不使用任何内建的哈希表库设计一个哈希集合
    具体地说，你的设计应该包含以下的功能
    add(value)：向哈希集合中插入一个值。
    contains(value) ：返回哈希集合中是否存在这个值。
    remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例

  • MyHashSet hashSet = new MyHashSet();
    hashSet.add(1);
    hashSet.add(2);
    hashSet.contains(1); // 返回 true
    hashSet.contains(3); // 返回 false (未找到)
    hashSet.add(2);
    hashSet.contains(2); // 返回 true
    hashSet.remove(2);
    hashSet.contains(2); // 返回 false (已经被删除)

python代码

  • 思路：利用字典，add时将key作为键，其对应的值设为1；remove时，将key对应的值设为0；检查是否存在时，如果字典中有key，返回其值是否等于1，若无则返回False
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
39
class MyHashSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data  = {}

    def add(self, key):
        """
        :type key: int
        :rtype: void
        """
        self.data[key] = 1

    def remove(self, key):
        """
        :type key: int
        :rtype: void
        """
        self.data[key] = 0 
        

    def contains(self, key):
        """
        Returns true if this set contains the specified element
        :type key: int
        :rtype: bool
        """
        if key in self.data:
            return self.data[key] == 1
        return False


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key

C++代码

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
class MyHashSet {
public:
    /** Initialize your data structure here. */
    vector<bool> data;
    MyHashSet() {
        data = vector<bool>(1000001,false);
    }
    
    void add(int key) {
        data[key]=true;
    }
    
    void remove(int key) {
        data[key]=false;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return data[key];
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * bool param_3 = obj.contains(key);
 */

706. 设计哈希映射

难度:容易

要求

  • 不使用任何内建的哈希表库设计一个哈希映射
    具体地说，你的设计应该包含以下的功能:
    put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
    get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
    remove(key)：如果映射中存在这个键，删除这个数值对。

示例

  • MyHashMap hashMap = new MyHashMap();
    hashMap.put(1, 1);
    hashMap.put(2, 2);
    hashMap.get(1); // 返回 1
    hashMap.get(3); // 返回 -1 (未找到)
    hashMap.put(2, 1); // 更新已有的值
    hashMap.get(2); // 返回 1
    hashMap.remove(2); // 删除键为2的数据
    hashMap.get(2); // 返回 -1 (未找到)

Python代码

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
39
40
41
42
43
44
45
46
class MyHashMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        

    def put(self, key, value):
        """
        value will always be non-negative.
        :type key: int
        :type value: int
        :rtype: void
        """
        self.data[key] = value

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        if key in self.data:
            return self.data[key]
        else:
            return -1

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: void
        """
        if key in self.data:
            del self.data[key]
        else:
            return


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

217. 存在重复元素

难度:容易

要求

  • 给定一个整数数组，判断是否存在重复元素。
    如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例

  • 输入: [1,2,3,1]
    输出: true
  • 输入: [1,2,3,4]
    输出: false

Python代码

  • 我的
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        len_1 = len(nums)
        ans = set()
        for i in nums:
            ans.add(i)
        len_2 = len(ans)
        return (len_1 != len_2)
  • 大佬的
1
2
3
4
5
6
7
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(set(nums)) != len(nums)

136. 只出现一次的数字

难度:容易

要求

  • 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    说明：
    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例

  • 输入: [2,2,1]
    输出: 1
  • 输入: [4,1,2,1,2]
    输出: 4

Python代码

  • 我的：采用了字典统计每个数出现的次数，最后返回次数为1的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = {}
        for i in nums:
            if i not in count:
                count[i] = 1
            else:
                count[i] += 1
        for j in count.keys():
            if count[j] == 1:
                return j
  • 大佬的：利用了异或的性质，出现了两次的异或后为0，出现了一次的与0异或得本身，最后返回即可
1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a=nums[0]
        for i in range(1,len(nums)):
            a=a^nums[i]
        return a

349. 两个数组的交集

难度:容易

要求

  • 给定两个数组，编写一个函数来计算它们的交集。

示例

  • 输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2]
  • 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [9,4]

Python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1 = set(nums1)
        nums2 = set(nums2)
        
        ans = []
        
        for i in nums2:
            if i in nums1:
                ans.append(i)
        
        return ans

202. 快乐数

难度:容易

要求

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

示例

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

Python代码

思路: 平方和会进入到循环中： 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，所以当平方和为这些循环中的值时，就不是快乐数，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """  
        list1 = [4,16, 37, 58, 89, 145,42, 20]
        while(n != 1):
            temp = 0
            while(n>0):
                temp += (n%10) * (n%10)
                n = n/10
            if temp in list1:
                return False
            n = temp      
        return True

1. 两数之和

难度:容易

要求

  • 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，
    并返回他们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例

  • 给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

Python代码

  • 思路：建立一个字典，键为nums[i],值为下标i,遍历数组时，检查差值是否在字典中，若在，返回两个数的下标即可
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in dic:
                return [dic[complement], i]
            dic[nums[i]] = i

205. 同构字符串

要求

  • 给定两个字符串 s 和 t，判断它们是否是同构的。
    如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
    所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例

  • 输入: s = “egg”, t = “add”
    输出: true

  • 输入: s = “foo”, t = “bar”
    输出: false

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return self.iso(s,t) and self.iso(t,s)
        
    def iso(self,s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        mapx = {}
        for i in range(len(s)):
            if s[i] not in mapx:
                mapx[s[i]] = t[i]
            elif s[i] in mapx:
                if t[i] != mapx[s[i]]:
                    return False
        return True

599. 两个列表的最小索引总和

难度:容易

要求

  • 假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
    你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。

示例

  • 输入：
    [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
    [“KFC”, “Shogun”, “Burger King”]
    输出: [“Shogun”]
    解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        dic = {}
        for i in range(len(list1)):
            if list1[i] in list2:
                sum_index = i + list2.index(list1[i])
                if sum_index not in dic:
                    dic[sum_index] = []
                dic[sum_index].append(list1[i])
        min_key = min(dic.keys())
        return dic[min_key]

387. 字符串中的第一个唯一字符

难度:容易

要求

  • 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例

  • s = “leetcode”
    返回 0.

  • s = “loveleetcode”,
    返回 2.

python代码

  • 维护一个hash表，键为字符，值为出现个数，返回第一个值为1的键的下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        str_hash = {}
        for i in range(len(s)):
            if s[i] not in str_hash:
                str_hash[s[i]] = 0
            str_hash[s[i]] += 1
        for i in str_hash.keys():
            if str_hash[i] == 1:
                return s.index(i)
        return -1

350. 两个数组的交集 II

难度:容易

要求

  • 给定两个数组，编写一个函数来计算它们的交集。

示例

  • 输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2,2]

  • 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [4,9]

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dic = {}
        ans = []
        for i in nums1:
            if i not in dic:
                dic[i] = 0
            dic[i] += 1
        for i in nums2:
            if i in dic and dic[i] != 0:
                ans.append(i)
                dic[i] -= 1
        return ans

219. 存在重复元素 II

难度:容易

要求

  • 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例

  • 输入: nums = [1,2,3,1], k = 3
    输出: true

  • 输入: nums = [1,0,1,1], k = 1
    输出: true

  • 输入: nums = [1,2,3,1,2,3], k = 2
    输出: false

Python代码

  • 题目意思描述的不是很清楚，其实想表达的意思是在k个距离之内，nums中是否存在重复，可以用一个字典，键为nums中的数值，值为数值对应的下标，如果出现重复则计算下标差值是否在k之内，若在，则返回True，否则更新该数值所对应的字典中的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        distance = {}
        for i in range(len(nums)):
            if nums[i] not in distance:
                distance[nums[i]] = i
            else:
                if i - distance[nums[i]] <= k:
                    return True
                else:
                    distance[nums[i]] = i
        return False

49. 字母异位词分组

难度:中等

要求

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

python代码

  • 思路：建立一个键值对，其中键的设计很重要，键可以设计成每一个字符串排序后的结果，这样每读取一个字符串，先进行一次重排，如果重排后的新串在字典中，则将原本的字符串插入到该键对应的值中，如果不在字典中，则建立一个新的键值对
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
class Solution:
    def rebuild(self, str):
        """
        重排字符串
        """
        ans = []
        for i in str:
            ans.append(i)
        ans.sort()
        return ''.join(ans)
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = {}
        for str in strs:
            if str in dic:
                dic[str].append(str)
                continue
            str_ = self.rebuild(str)
            if str_ not in dic:
                dic[str_] = []
            dic[str_].append(str)
        return list(dic.values())

36. 有效的数独

难度:中等

要求

  • 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

示例

  • 输入:
    [
    [“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],
    [“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],
    [“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],
    [“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],
    [“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],
    [“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],
    [“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],
    [“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],
    [“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]
    ]
    输出: true

  • 输入:
    [
    [“8”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],
    [“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],
    [“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],
    [“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],
    [“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],
    [“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],
    [“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],
    [“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],
    [“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]
    ]
    输出: false
    解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

python代码

  • 思路：建立三个函数，分别是判断题目中的三个要求
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
class Solution:
    def isValidRow(self, board):   
        for i in range(9):
            list_ = []
            for j in range(9):
                if board[i][j] != '.' and board[i][j] in list_:
                    return False
                list_.append(board[i][j])
        return True

    def isValidColumn(self, board):
        for j in range(9):
            list_ = []
            for i in range(9):
                if board[i][j] != '.' and board[i][j] in list_:
                    return False
                list_.append(board[i][j])
        return True
                
    def isValidSquare(self, board):
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                list_ = []
                for k in range(i, i+3):
                    for l in range(j, j+3):
                        if board[k][l] != '.' and board[k][l] in list_:
                            return False
                        list_.append(board[k][l])
        return True
    
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        return self.isValidRow(board) and self.isValidColumn(board) and self.isValidSquare(board)

652. 寻找重复的子树

难度:中等

要求

  • 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
    两棵树重复是指它们具有相同的结构以及相同的结点值。

Python 代码

  • 思路：对每一个子树采用先序遍历的方法，将遍历的结果保存为字符串作为键，值设为出现的次数，若值为1，则将子串的root添加到ans中，最后返回ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def helper(self, root, dic, ans):
        if root is None:
            return '#'
        dic_key = str(root.val)+','+self.helper(root.left, dic, ans)+','+self.helper(root.right, dic, ans)
        if dic_key not in dic:
            dic[dic_key] = 0
        elif dic[dic_key] == 1:
            ans.append(root)
        dic[dic_key] += 1
        return dic_key
    
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        dic = {}
        ans = []
        self.helper(root, dic, ans)
        return ans

771.宝石与石头

难度:容易

要求

  • 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此”a”和”A”是不同类型的石头。

示例

  • 输入: J = “aA”, S = “aAAbbbb”
    输出: 3

  • 输入: J = “z”, S = “ZZ”
    输出: 0

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numJewelsInStones(self, J, S):
        """
        :type J: str
        :type S: str
        :rtype: int
        """
        dic = {}
        for i in J:
            dic[i] = 0
        for j in S:
            if j in dic:
                dic[j] += 1
        return sum(dic.values())

3.无重复字符的最长子串

难度:中等

要求

  • 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例

  • 示例 1:
    输入: “abcabcbb”
    输出: 3
    解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

  • 示例 2:
    输入: “bbbbb”
    输出: 1
    解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

  • 示例 3:
    输入: “pwwkew”
    输出: 3
    解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

python代码

  • 思路：维护一个列表，依次读取s中的字符，如果该字符不在列表中，则加入，并更新最大长度，若在列表中，则删除掉列表中前面到该字符的全部元素，并将该字符插入到最后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        list_str = []
        for i in s:
            if i not in list_str:
                list_str.append(i)
                max_length = max_length if max_length > len(list_str) else len(list_str)
            else:
                del list_str[:list_str.index(i)+1]
                list_str.append(i)
        return max_length

454. 四数相加 II

难度:中等

思路

  • 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
    为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

示例

  • 输入:
    A = [ 1, 2]
    B = [-2,-1]
    C = [-1, 2]
    D = [ 0, 2]
    输出:
    2
    解释:
    两个元组如下:
  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Python 代码

  • 思路：维护一个字典，键为AB各取一个元素的和，值为这个和出现的次数，在CD中各取一个元素求和，去相反数，如果相反数在字典中，则ans加上这个相反数对应的值
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
class Solution:
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        length = len(A)
        dic_AB = {}
        ans = 0
        for i in range(length):
            for j in range(length):
                sum_AB = A[i] + B[j]
                if sum_AB not in dic_AB:
                    dic_AB[sum_AB] = 0
                dic_AB[sum_AB] += 1
        for i in range(length):
            for j in range(length):
                sum_CD = C[i] + D[j]
                if -sum_CD in dic_AB:
                    ans += dic_AB[-sum_CD]
                    
        return ans

347. 前K个高频元素

难度:中等

要求

  • 给定一个非空的整数数组，返回其中出现频率前 k 高的元素

示例

  • 示例 1:
    输入: nums = [1,1,1,2,2,3], k = 2
    输出: [1,2]

  • 示例 2:
    输入: nums = [1], k = 1
    输出: [1]

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dic = {}      
        for i in nums:
            if i not in dic:
                dic[i] = 0
            dic[i] += 1
        a = sorted(dic.items(), key=lambda item:item[1],reverse=True) 
        # 按值排序，reverse默认为False，为升序，True为降序，返回的是一个列表，列表元素为有序的键值元组
        ans = []
        for i in range(k):
            ans.append(a[i][0])
        return ans

380. 常数时间插入、删除和获取随机元素

难度:中等

要求

  • 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
    insert(val)：当元素 val 不存在时，向集合中插入该项。
    remove(val)：元素 val 存在时，从集合中移除该项。
    getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例

  • // 初始化一个空的集合。
    RandomizedSet randomSet = new RandomizedSet();
    // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
    randomSet.insert(1);
    // 返回 false ，表示集合中不存在 2 。
    randomSet.remove(2);
    // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
    randomSet.insert(2);
    // getRandom 应随机返回 1 或 2 。
    randomSet.getRandom();
    // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
    randomSet.remove(1);
    // 2 已在集合中，所以返回 false 。
    randomSet.insert(2);
    // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
    randomSet.getRandom();

Python代码

  • 思路：既然是要求在常数时间内的操作，很自然想到要用到数组的序号来操作，这里维护一个字典和一个列表，字典的键为元素，字典值为该元素在列表中的序号
  • 在插入时，字典和列表均插入元素，字典中的值设为列表中元素的序号
  • 在删除时，先在字典中获取待删除元素的序号，在列表中将末尾元素替换至该序号处，在字典中修改替换过来的元素的值，最后pop掉列表最后一个元素，同时删除掉字典中的val
  • 在随机获取时，使用random随机获取一个序号，然后返回列表中对应序号的元素
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import random
class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.dic = {}
        self.lst = []

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        
        if val not in self.dic:
            self.lst.append(val)
            self.dic[val] = len(self.lst) - 1
            return True
        return False
        
        
    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        
        if val in self.dic:
            idx = self.dic[val]
            self.lst[idx] = self.lst[-1]  # 与末尾元素交换
            self.dic[self.lst[idx]] = idx # 修改字典中交换元素的值
            self.lst.pop()
            del self.dic[val]
            return True
        return False
    
    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        
        idx = random.randint(0, len(self.lst)-1)
        return self.lst[idx]
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
-------------本文结束 感谢您的阅读-------------