北大硕士LeetCode算法专题课-查找相关问题

r囧r小猫 2024-03-30 17:29 12阅读 0赞

**黑马算法面试专题**

[北大硕士LeetCode算法专题课-字符串相关问题][LeetCode_-][ 北大硕士LeetCode算法专题课-数组相关问题\_][_LeetCode_-]

[北大硕士LeetCode算法专题课-基础算法查找\_][LeetCode_- 1]

[北大硕士LeetCode算法专题课-基础算法之排序\_客][LeetCode_- 2]

[北大硕士LeetCode算法专题课---算法复杂度介绍\_客][LeetCode_---]

**查找相关问****题**

查找有无：

某个 元素是否存在 通过集合（set） 可以解决这一类问题

查找对应关系：

某个元素出现了几次， 返回满足条件元素的下标， 通过字典 （Dict）可以解决这一类问题

查找问题中经常要用到集合与字典， 要熟悉相关API

![f70890c8e61d4f7694eef4a6189ce4d8.png][]

![a5de289f80004dc9b930c95091bcff6c.png][]

**两个数组的交集** **(LeetCode349)**

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

![c3d52e55cae44266be3ec7d4545ffecf.png][]

![a6e4c0ce6c2e48beaade86623c298f05.png][]

![58b016411c86459aa4fd59a733974a6c.png][]

时间复杂度：*O*(*m*log*m*\+*n*log

def intersection(nums1, nums2):  nums1.sort()
    nums2.sort()
    length1, length2 = len(nums1), len(nums2)  intersection = list()
    index1 = index2 = 0
    while index1 < length1 and index2 < length2:  num1 = nums1[index1]
    num2 = nums2[index2]
    if num1 == num2:
    if not intersection or num1 != intersection[-1]:  intersection.append(num1) # 保证加入元素的唯一性
    index1 += 1
    index2 += 1
    elif num1 < num2:  index1 += 1
    else:
    index2 += 1
    return intersection

思路二：利用set

def intersection( nums1, nums2):  """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]  """
    set1 = set(nums1)  set2 = set(nums2)
    if len(set2)> len(set1):
    return [x for x in set1 if x in set2]
    else:
    return [x for x in set2 if x in set1]

时间复杂度：O(m+n)

**两个数组的交集** **II(LeetCode350)**

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，

应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序

![14de6a8d80234528857d5ba08c69b1e7.png][]

def intersect(nums1, nums2):  nums1.sort()  nums2.sort()
    
    length1, length2 = len(nums1), len(nums2)  intersection = list()
    index1 = index2 = 0
    while index1 < length1 and index2 < length2:
    if nums1[index1] < nums2[index2]:  index1 += 1
    elif nums1[index1] > nums2[index2]:  index2 += 1
    else:
    intersection.append(nums1[index1])  index1 += 1
    index2 += 1
    
    return intersection

**两个数组的交集** **II(LeetCode350)**

思路二：利用字典

![d35d3ee1bbd34239ae97f5a9429a19d0.png][]

def intersect2(nums1, nums2):
    if len(nums1) > len(nums2):
    return intersect2(nums2, nums1)
    
    m = collections.Counter()
    for num in nums1:  m[num] += 1
    
    intersection = list()
    for num in nums2:
    if m.get(num, 0) > 0:  intersection.append(num)  m[num] -= 1
    if m[num] == 0:  m.pop(num)
    
    return intersection

**复杂度分析****：**

时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度

空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度

**同构字符串** **(LeetCode205)**

给定两个字符串 s 和 t ，判断它们是否同构。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映 射到同一个字符上，字符可以映射到自己本身。

![0a7adee399ae4f15a50635968f595f5b.png][]

使用字典构建查找表

![fbe3386e6ff24e8ab2be8452cdb21a54.png][]

def isIsomorphic(s, t):
    if len(t) != len(s):
    return False  dict_s = {}  dict_t = {}
    for i in range(len(s)):
    s_char, t_char = s[i], t[i]
    if s_char not in dict_s:  dict_s[s_char] = t_char
    if t_char not in dict_t:  dict_t[t_char] = s_char
    if dict_s[s_char] != t_char or dict_t[t_char] != s_char:
    return False
    return True

**复****杂度分析****：**时间复杂度：O(n)

**两数之和** **(LeetCode** **1)**

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

你可以按任意顺序返回答案。

![36b98ffaa96f4e0e8f19fe1df52f735b.png][]**两数之和** **(LeetCode** **1)**

解法一 暴力解法 双重for循环O(N2)

解法二：使用查找表（dict），可以将寻找 target \- x 的时间复杂度降低到从 O(N) 降低到 O(1)。

创建一个字典，对于每一个 x，首先查询字典中是否存在 target \- x，然后将 x 插入到字典中，即可保证不会让 x 和自己匹配。

def twoSum(nums, target):  hashtable = dict()
    for i, num in enumerate(nums):
    if target - num in hashtable:
    return [hashtable[target - num], i]  hashtable[nums[i]] = i
    return []

**复杂度分析****：**时间复杂度：时间复杂度：O(N)，其中 N是数组中的元素数量。Python dict 查找时间复杂度O(1) 空间复杂度：O(N)

**四数相加** **II** **(LeetCode454)** **中****等**

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

l 0 <= i, j, k, l < n

l nums1\[i\] + nums2\[j\] + nums3\[k\] + nums4\[l\] == 0

示例 1：

输入：nums1 = \[1,2\], nums2 = \[-2,-1\], nums3 = \[-1,2\], nums4 = \[0,2\]

输出：2 提示 1 <= n <= 200

解释：

1. (0, 0, 0, 1) -> nums1\[0\] + nums2\[0\] + nums3\[0\] + nums4\[1\] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> nums1\[1\] + nums2\[1\] + nums3\[0\] + nums4\[0\] = 2 + (-1) + (-1) + 0 = 0

![64abc7fc1a2b478bb01cf6a2e0072eb6.png][]

将四个数组分成两部分，A 和 B 为一组，C 和 D 为另外一组。

对于 A 和 B，我们使用二重循环对它们进行遍历，得到所有 A\[i\]+B\[j\] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每 个键表示一种 A\[i\]+B\[j\]，对应的值为 A\[i\]+B\[j\]出现的次数。

对于 C 和 D，我们同样使用二重循环对它们进行遍历。当遍历到 C\[k\]+D\[l\] 时，如果 \-(C\[k\]+D\[l\]) 出现在哈希映射中，那么将 \- (C\[k\]+D\[l\]) 对应的值累加进答案中。

最终即可得到满足 A\[i\]+B\[j\]+C\[k\]+D\[l\]=0=的四元组数目。

**复杂度分析：**时间复杂度：O(n2) 空间复杂度：O(n2)

def fourSumCount(A, B, C, D):
    countAB = collections.Counter(u + v for u in A for v in B)  ans = 0
    for u in C:
    for v in D:
    if -u - v in countAB:
    ans += countAB[-u - v]
    return ans

**存在重复元素** **II** **(LeetCode** **219)**

给你一个整数数组nums和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足nums\[i\] == nums\[j\] 且 abs(i \- j) <= k 。 如果存在，返回 true ；否则，返回 false 。

![e2f3dbf90c0a4b9a8534998002b16b3c.png][]

解法1 创建字典用于查找，遍历的过程中，判断在字典中是否存在满足条件的key，如果满足直接返回True，如不满足，则将数 组中元素不断放入字典中， key为数值， value为索引

def containsNearbyDuplicate(nums, k):  pos = {}
    for i, num in enumerate(nums):
    if num in pos and i - pos[num] <= k:
    return True  pos[num] = i
    return False

解法2 滑动窗口, 创建一个set 用来保存窗口中数据, 当扩大窗口时, 如果从set中能取到新加入的值, 说明有满足条件的元素

![0b991c3157c34e659dcddefc9418c595.png][]

![164a1411fb4b4651881e11bc1bcbe5c7.png][]

![a00ad6e0bd1e49e1b600dd53ab31d4fc.png][]

![83f7e3b962d346d49e2ddd863b068bef.png][]

解法2 滑动窗口

def containsNearbyDuplicate2(nums, k):  s = set()
    for i, num in enumerate(nums):
    if i > k:
    s.remove(nums[i - k - 1])
    if num in s:
    return True  s.add(num)
    return False

**复杂度分析****：**时间复杂度：O(n) 空间复杂度：O(n)

[LeetCode_-]: https://blog.csdn.net/JACK_SUJAVA/article/details/128642376
[_LeetCode_-]: https://blog.csdn.net/JACK_SUJAVA/article/details/128626964
[LeetCode_- 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128625648
[LeetCode_- 2]: https://blog.csdn.net/JACK_SUJAVA/article/details/128624508
[LeetCode_---]: https://blog.csdn.net/JACK_SUJAVA/article/details/128611560
[f70890c8e61d4f7694eef4a6189ce4d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d27d800778154dee9b4bd3564000917a.png
[a5de289f80004dc9b930c95091bcff6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f73694b5b8444b839f2e7485eac2c804.png
[c3d52e55cae44266be3ec7d4545ffecf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dbcfbfaf766e48bf8799b4810e27e0b9.png
[a6e4c0ce6c2e48beaade86623c298f05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/21c106aa027e4b4f976b3837ab714fd3.png
[58b016411c86459aa4fd59a733974a6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e2a28c6c22ea4529a5dd85d4eef804e6.png
[14de6a8d80234528857d5ba08c69b1e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/17173ae958854ae8becd3c06b46f6dba.png
[d35d3ee1bbd34239ae97f5a9429a19d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/78bf1a9898cd436a88436fbde8f2773f.png
[0a7adee399ae4f15a50635968f595f5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/854a581bb46c4c44a8ce9c3516b65e05.png
[fbe3386e6ff24e8ab2be8452cdb21a54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/08ac1cd57d5f4cc5aa6f281c0f10d9c1.png
[36b98ffaa96f4e0e8f19fe1df52f735b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ec6fc4f2dad04e65967668f423c46b5c.png
[64abc7fc1a2b478bb01cf6a2e0072eb6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0bdc0ccf09f143759b2dad4addf8cfc1.png
[e2f3dbf90c0a4b9a8534998002b16b3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/230bd8df830b4691bd9f1888fd2f6aa7.png
[0b991c3157c34e659dcddefc9418c595.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5c0e46fe32fb4f7e980937363045b0b4.png
[164a1411fb4b4651881e11bc1bcbe5c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/988f0abdd86f490ea052741cec531243.png
[a00ad6e0bd1e49e1b600dd53ab31d4fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ad1e567d6e214d48a119c3822b2384d7.png
[83f7e3b962d346d49e2ddd863b068bef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8b8337c79c3d4273a87c25505d928f49.png