最小公共值
难度:
标签:
题目描述
Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1.
Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.
Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4] Output: 2 Explanation: The smallest element common to both arrays is 2, so we return 2.
Example 2:
Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5] Output: 2 Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.
Constraints:
1 <= nums1.length, nums2.length <= 1051 <= nums1[i], nums2[j] <= 109- Both
nums1andnums2are sorted in non-decreasing order.
代码结果
运行时间: 30 ms, 内存: 36.1 MB
/*
* 思路：
* 1. 将nums1和nums2转换为Stream。
* 2. 使用filter筛选出在两个数组中都存在的元素。
* 3. 使用findFirst找到最小的公共元素。
* 4. 如果找到则返回该元素，否则返回-1。
*/
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.stream.IntStream;
public class Solution {
public int findSmallestCommonElement(int[] nums1, int[] nums2) {
OptionalInt result = Arrays.stream(nums1)
.filter(num -> IntStream.of(nums2).anyMatch(n -> n == num))
.findFirst();
return result.orElse(-1);
}
}解释
方法:
题解的思路是先将其中一个数组（这里是nums2）的元素存储在一个集合中，这样可以利用集合的O(1)时间复杂度的查找特性。然后，遍历另一个数组（nums1），对于每个元素，检查它是否存在于之前创建的集合中。一旦发现第一个公共元素，立即返回该元素。如果遍历完整个数组都没有找到公共元素，则返回-1。
时间复杂度:
O(m + n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择将nums2的元素放入集合中，而不是nums1的元素？这种选择对算法的性能有什么影响？
▷🦆
在创建集合时，对nums2中的重复元素是如何处理的？集合是否自动去重，这对性能有何影响？
▷🦆
在检查每个元素是否存在于集合中时，如果元素不存在，算法是如何处理的？是否有额外的性能开销？
▷🦆
这种方法在处理非常大的数据集时（接近上限1e5），性能表现如何？有没有可能出现内存不足的情况？
▷