Question

2540. 最小公共值

English Version

题目描述

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

如果一个整数在两个数组中都 至少出现一次 ，那么这个整数是数组 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 <= 105
• 1 <= nums1[i], nums2[j] <= 109
• nums1 和 nums2 都是 非降序 的。

解法

方法一：双指针

遍历两个数组，如果两个指针指向的元素相等，则返回该元素；如果两个指针指向的元素不相等，则将指向较小元素的指针右移一位，直到找到相等的元素或者遍历完数组。

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

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

class Solution {
  public int getCommon(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    for (int i = 0, j = 0; i < m && j < n;) {
      if (nums1[i] == nums2[j]) {
        return nums1[i];
      }
      if (nums1[i] < nums2[j]) {
        ++i;
      } else {
        ++j;
      }
    }
    return -1;
  }
}

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

func getCommon(nums1 []int, nums2 []int) int {
  m, n := len(nums1), len(nums2)
  for i, j := 0, 0; i < m && j < n; {
    if nums1[i] == nums2[j] {
      return nums1[i]
    }
    if nums1[i] < nums2[j] {
      i++
    } else {
      j++
    }
  }
  return -1
}

function getCommon(nums1: number[], nums2: number[]): number {
  const m = nums1.length;
  const n = nums2.length;
  let i = 0;
  let j = 0;
  while (i < m && j < n) {
    if (nums1[i] === nums2[j]) {
      return nums1[i];
    }
    if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return -1;
}

impl Solution {
  pub fn get_common(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let m = nums1.len();
    let n = nums2.len();
    let mut i = 0;
    let mut j = 0;
    while i < m && j < n {
      if nums1[i] == nums2[j] {
        return nums1[i];
      }
      if nums1[i] < nums2[j] {
        i += 1;
      } else {
        j += 1;
      }
    }
    -1
  }
}

int getCommon(int* nums1, int nums1Size, int* nums2, int nums2Size) {
  int i = 0;
  int j = 0;
  while (i < nums1Size && j < nums2Size) {
    if (nums1[i] == nums2[j]) {
      return nums1[i];
    }
    if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return -1;
}

方法二

impl Solution {
  pub fn get_common(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let mut iter1 = nums1.iter();
    let mut iter2 = nums2.iter();
    let mut num1 = iter1.next();
    let mut num2 = iter2.next();

    while let (Some(n1), Some(n2)) = (num1, num2) {
      if n1 == n2 {
        return *n1;
      } else if n1 < n2 {
        num1 = iter1.next();
      } else {
        num2 = iter2.next();
      }
    }

    -1
  }
}