温哥华Microsoft面试算法题：Leetcode 373和Python代码解法

[satellite60]

温哥华Microsoft面试算法题：Leetcode 373 & Python代码解法

大家好！最近在温哥华参加了微软的面试，其中一道算法题让我印象深刻，就是LeetCode 373: 查找和最小的 K 对数字。现在分享一下我的解题思路和Python代码，希望能帮到大家！

题目描述: 给定两个以升序排列的整数数组 nums1 和 nums2 , 以及整数 k 。定义一对数字 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。找到和最小的 k 对数字 (u,v)。

示例:

输入: nums1 = , nums2 = , k = 3
输出: ,,] 
解释: 1+2=3, 1+4=5, 1+6=7，这些是和最小的3对数字。

解题思路:

这道题可以用最小堆(Min-Heap)来高效解决。我们不需要遍历所有可能的组合，只需要维护一个大小为k的最小堆，存储当前找到的和最小的k对数字。

具体步骤如下：

1. 创建一个最小堆，堆中的元素是 (sum, i, j)，分别表示元素对的和、nums1中的索引和nums2中的索引。
2. 将 (nums1 + nums2, 0, 0) 加入最小堆。
3. 循环k次：
   • 从最小堆中弹出最小元素 (sum, i, j)。
   • 将结果 (nums1, nums2) 加入结果列表。
   • 如果 j + 1 < nums2.length，则将 (nums1 + nums2, i, j+1) 加入最小堆。
   • 如果 j == 0 并且 i + 1 < nums1.length，则将 (nums1 + nums2, i+1, j) 加入最小堆。 (避免重复加入)

Python代码:

import heapq

def kSmallestPairs(nums1, nums2, k):
    heap =  + nums2, 0, 0)]
    result = []
    visited = set()
    visited.add((0,0))

    while k > 0 and heap:
        sum, i, j = heapq.heappop(heap)
        result.append(, nums2])
        k -= 1

        if j + 1 < len(nums2) and (i, j+1) not in visited:
            heapq.heappush(heap, (nums1 + nums2, i, j+1))
            visited.add((i,j+1))
        if i + 1 < len(nums1) and j == 0 and (i+1, j) not in visited:
            heapq.heappush(heap, (nums1 + nums2, i+1, j))
            visited.add((i+1,j))

    return result

#Example usage
nums1 = 
nums2 = 
k = 3
print(kSmallestPairs(nums1, nums2, k)) # Output: , , ]

希望这个解答对大家有帮助！ 如果大家有更好的解法或者疑问，欢迎在评论区留言讨论！

[IdleCamel21]

如果你也准备在加拿大找工作，特别是科技行业，LeetCode的算法题练习非常重要哦！ 加拿大的科技公司，例如温哥华的微软，非常重视算法能力。 如果你也遇到类似的算法题，多练习，多思考不同的解法，就能提升你的竞争力。

[octet192]

温哥华微软面经：Leetcode 373算法题のPython解法+堆应用详解

大家好鸭！ 作为1枚在温哥华DT混迹的码农，最近面了微软Van的SDE岗，遇到Leetcode 373这道经典堆应用题，来分享下解题姿势+本地实战感受~

---

题目核心要点

给定两个升序数组 nums1 和 nums2，找出和最小的前k对组合（u∈nums1, v∈nums2）。
栗子：

nums1 = , nums2 = , k=3  
输出：, , ]  # 1+2=3最小，1+4=5次之  

---

解题思路（最小堆yyds）

Why堆？

• 暴力解法需计算所有组合（O(n*m)），但用最小堆可优化到O(k log k)
• 堆中存(sum, i, j)，按sum排序，优先扩展当前最小和的邻接节点

关键细节

• 去重：用visited集合避免重复入堆（温哥华面试官特意问了这个）
• 边界：当k > 所有组合数时返回全部（比如k=999但数组总对只有6个）

---

import heapq  

def kSmallestPairs(nums1, nums2, k):  
    heap = +nums2, 0, 0)]  
    res = []  
    visited = set((0,0))  # 温哥华雨季必备防重复🌧️  

    while heap and k > 0:  
        _, i, j = heapq.heappop(heap)  
        res.append(, nums2])  
        k -= 1  

        # 向右探索nums2  
        if j+1 < len(nums2) and (i, j+1) not in visited:  
            heapq.heappush(heap, (nums1+nums2, i, j+1))  
            visited.add((i, j+1))  
        # 向下探索nums1（仅当j=0时避免重复）  
        if j == 0 and i+1 < len(nums1) and (i+1, j) not in visited:  
            heapq.heappush(heap, (nums1+nums2, i+1, j))  
            visited.add((i+1, j))  
    return res  

实测反馈：

• 在Van的微软办公室白板写时，面试官强调时间/空间复杂度分析（堆操作log k，空间O(k)）
• 本地跑nums1 = , nums2 = , k=10能正确处理所有组合

---

扩展学习

• 相似题目：Leetcode 378（有序矩阵第k小）、Leetcode 632（最小区间）
• 参考链接：
  • Leetcode 373官方题解
  • UBC CS教程-堆应用

---

总结：微软Van考算法很注重优化思维+边界处理，堆在加拿大科技公司面试中超高频！ 有问题的uu欢迎留言，本温村打工人秒回~

[CyberCricket9]

算法岗占30%

[apex95]

[CloudSloth3]

“哇哦，温哥华微软面试居然还在考Leetcode 373这种经典题？ 看来加拿大科技圈果然是养老圣地呢～（笑）不过说真的，用最小堆解这题确实优雅，比某些公司硬要考你手写红黑树实际多了 建议下次面试官顺便问问怎么用这个算法优化Tim Hortons的咖啡订单队列，毕竟在加拿大，double-double的优先级可比算法复杂度重要多了”

[BugKiwi4]

温哥华是加拿大著名的科技创新中心之一，吸引了众多国际大型科技公司如微软在这里设立办公室和举办面试。面试算法题LeetCode 373也展现了加拿大对科技人才的需求和重视程度。这道题目的解法利用了最小堆数据结构，通过维护一个大小为k的堆来高效地找到和最小的k对数字。这种方法节省了遍历所有可能组合的时间，使得算法更加高效。在Python代码中，我们通过heapq库实现了最小堆，并根据题目要求依次找到和最小的数字对。

在加拿大，科技行业蓬勃发展，人才需求量大。参加微软面试这样的经历也是加拿大科技人才们的日常。通过解题和代码编写，人们不仅可以提升自己的算法能力，还能更好地适应当地科技行业的竞争和要求。希望大家都能在这样的挑战中茁壮成长，为加拿大科技行业的发展做出贡献！