Easy

题目描述

给你两个整数数组 nums1 和 nums2，它们已经按非递减顺序排列，请你返回两个数组中 公共的、最小的 整数。如果两个数组中没有公共整数，请你返回 -1。

注意，如果一个整数在 nums1 和 nums2 中都 至少出现一次，那么这个整数就是 nums1 和 nums2 公共的。

示例 1：

输入：nums1 = [1,2,3], nums2 = [2,4]
输出：2
解释：两个数组中的公共元素是 2，所以返回 2。

示例 2：

输入：nums1 = [1,2,3,6], nums2 = [2,3,4,5]
输出：2
解释：两个数组中有两个公共元素：2 和 3，其中 2 是较小的，所以返回 2。

提示：

  • 1 <= nums1.length, nums2.length <= 10^5
  • 1 <= nums1[i], nums2[j] <= 10^9
  • nums1 和 nums2 都按 非递减顺序 排列。

解题思路

由于两个数组都是有序的，我们可以利用这个特性来高效地找到最小公共值。

方法一：双指针法（推荐）

使用两个指针分别指向两个数组的开头。比较两个指针指向的元素：

  • 如果相等，找到公共元素，直接返回
  • 如果 nums1[i] < nums2[j]，说明当前 nums1[i] 不可能在 nums2 中找到匹配，移动 i 指针
  • 如果 nums1[i] > nums2[j]，说明当前 nums2[j] 不可能在 nums1 中找到匹配，移动 j 指针

由于数组有序，第一个找到的公共元素就是最小的。

方法二：哈希集合法

将较短的数组元素存入哈希集合，然后遍历另一个数组查找公共元素。虽然简单，但空间复杂度较高。

方法三：二分搜索法

对于较短数组的每个元素，在较长数组中进行二分搜索。但在最坏情况下时间复杂度不如双指针法。

双指针法充分利用了数组有序的特性，时间复杂度最优，是此题的最佳解法。

代码实现

class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        int i = 0, j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                return nums1[i];
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        return -1;
    }
};

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        i, j = 0, 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                return nums1[i]
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        
        return -1

public class Solution {
    public int GetCommon(int[] nums1, int[] nums2) {
        int i = 0, j = 0;
        
        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i] == nums2[j]) {
                return nums1[i];
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        return -1;
    }
}

var getCommon = function(nums1, nums2) {
    let i = 0, j = 0;
    
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针法哈希集合法
时间复杂度O(m + n)O(m + n)
空间复杂度O(1)O(min(m, n))

其中 m 和 n 分别为两个数组的长度。双指针法在空间复杂度上更优。

相关题目