企业官网建设流程全解析

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你两个整数数组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 <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^9
• nums1和nums2都是非降序的。

方法 双指针

设n nn是n u m s 1 nums_1nums1​的长度，m mm是n u m s 2 nums_2nums2​的长度。找最小公共值，首先关注两个数组的最小值，也就是比较x = n u m s 1 [ 0 ] x=nums_1[0]x=nums1​[0]和y = n u m s 2 [ 0 ] y = nums_2[0]y=nums2​[0]的大小：

• 如果x = y x=yx=y，由于两个数组都是递增的，所以x xx是最小的公共值；
• 如果x < y x < yx<y，那么x xx也小于n u m s 2 nums_2nums2​的其余元素，所以x xx不可能是公共值，排除，问题变成n u m s 1 nums_1nums1​的后缀[ 1 , n − 1 ] [1, n-1][1,n−1]和n u m s 2 nums_2nums2​的最小公共值。对于这个子问题，做法是一样的，比较n u m s 1 [ 1 ] nums_1[1]nums1​[1]和n u m s 2 [ 0 ] nums_2[0]nums2​[0]的大小。
• 如果x > y x > yx>y，那么y yy也小于n u m s 1 nums_1nums1​的其余元素，所以y yy不可能是公共值，排除，问题变成n u m s 1 nums_1nums1​和n u m s 2 nums_2nums2​的后缀[ 1 , m − 1 ] [1, m-1][1,m−1]的最小公共值。对于这个子问题，做法是一样的，比较n u m s 1 [ 0 ] nums_1[0]nums1​[0]和n u m s 2 [ 1 ] nums_2[1]nums2​[1]的大小。

用两个下标i ii和j jj表示当前要比较的n u m s 1 [ i ] nums_1[i]nums1​[i]和n u m s 2 [ j ] nums_2[j]nums2​[j]的大小。

classSolution{publicintgetCommon(int[]nums1,int[]nums2){inti=0,n=nums1.length;intj=0,m=nums2.length;while(i<n&&j<m){if(nums1[i]==nums2[j]){returnnums1[i];}if(nums1[i]<nums2[j]){i++;}else{j++;}}return-1;}}

classSolution{public:intgetCommon(vector<int>&nums1,vector<int>&nums2){inti=0,n=nums1.size();intj=0,m=nums2.size();while(i<n&&j<m){if(nums1[i]==nums2[j]){returnnums1[i];}if(nums1[i]<nums2[j]){i++;}else{j++;}}return-1;}};

classSolution:defgetCommon(self,nums1:List[int],nums2:List[int])->int:i,n=0,len(nums1)j,m=0,len(nums2)whilei<nandj<m:ifnums1[i]==nums2[j]:returnnums1[i]ifnums1[i]<nums2[j]:i+=1else:j+=1return-1# 写法2classSolution:defgetCommon(self,nums1:List[int],nums2:List[int])->int:returnmin(set(nums1)&set(nums2),default=-1)

funcgetCommon(nums1,nums2[]int)int{i,n:=0,len(nums1)j,m:=0,len(nums2)fori<n&&j<m{ifnums1[i]==nums2[j]{returnnums1[i]}ifnums1[i]<nums2[j]{i++}else{j++}}return-1}

implSolution{pubfnget_common(nums1:Vec<i32>,nums2:Vec<i32>)->i32{letn=nums1.len();letm=nums2.len();letmuti=0;letmutj=0;whilei<n&&j<m{ifnums1[i]==nums2[j]{returnnums1[i];}ifnums1[i]<nums2[j]{i+=1;}else{j+=1;}}-1}}

vargetCommon=function(nums1,nums2){leti=0,n=nums1.length;letj=0,m=nums2.length;while(i<n&&j<m){if(nums1[i]===nums2[j]){returnnums1[i];}if(nums1[i]<nums2[j]){i++;}else{j++;}}return-1;};

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

复杂度分析：

• 时间复杂度：O ( n + m ) O(n+m)O(n+m)，其中n nn是n u m s 1 nums_1nums1​的长度，m mm是n u m s 2 nums_2nums2​的长度。
• 空间复杂度：O ( 1 ) O(1)O(1)。

相似题目

[[Leetcode 350. 两个数组的交集 II]]
[[LeetCode 88. 合并两个有序数组【数组,双指针】简单]]