📢前言
🌲 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程😜 🌲 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题 🌲 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧🧐! 🌲 今天是力扣算法题持续打卡第52天🎈!
🌲原题样例:两个数组的交集
给定两个数组,编写一个函数来计算它们的交集。
示例:
输入:nums1 = [ 1 , 2 , 2 , 1 ] , nums2 = [ 2 , 2 ]
输出:[ 2 ]
示例 2:
输入:nums1 = [ 4 , 9 , 5 ] , nums2 = [ 9 , 4 , 9 , 8 , 4 ]
输出:[ 9 , 4 ]
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
🌻C#方法:排序
计算两个数组的交集,直观的方法是遍历数组 nums1,对于其中的每个元素,遍历数组 nums2 判断该元素是否在数组 nums2 中,如果存在,则将该元素添加到返回值。
假设数组 nums1 和 nums2 的长度分别是 m和 n,则遍历数组 nums1 需要 O(m) 的时间,判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间,因此总时间复杂度是O(mn)。
如果使用哈希集合存储元素,则可以在O(1) 的时间内判断一个元素是否在集合中,从而降低时间复杂度。
首先使用两个集合分别存储两个数组中的元素,然后遍历较小的集合,判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。
该方法的时间复杂度可以降低到 O(m+n)
代码:
public class Solution {
public int [ ] Intersection ( int [ ] nums1, int [ ] nums2) {
HashSet< int > set1 = new HashSet< int > ( ) ;
HashSet< int > set2 = new HashSet< int > ( ) ;
foreach ( int num in nums1)
{
set1. Add ( num) ;
}
foreach ( int num in nums2)
{
set2. Add ( num) ;
}
return GetIntersection ( set1, set2) ;
}
public int [ ] GetIntersection ( HashSet< int > set1, HashSet< int > set2)
{
if ( set1. Count ( ) > set2. Count ( ) )
{
return GetIntersection ( set2, set1) ;
}
HashSet< int > intersection = new HashSet< int > ( ) ;
foreach ( int num in set1)
{
if ( set2. Contains ( num) )
{
intersection. Add ( num) ;
}
}
int [ ] answer = new int [ intersection. Count ( ) ] ;
int i = 0 ;
foreach ( var num in intersection)
{
answer[ i] = num;
i++ ;
}
return answer;
}
}
执行结果
通过
执行用时:132 ms,在所有 C# 提交中击败了97.37 % 用户
内存消耗:40.6 MB,在所有 C# 提交中击败了5.26 % 的用户
🌻Java 方法:两个集合
思路解析
计算两个数组的交集,直观的方法是遍历数组 nums1,对于其中的每个元素,遍历数组 nums2 判断该元素是否在数组 nums2 中,如果存在,则将该元素添加到返回值。
假设数组 nums1 和 nums2 的长度分别是 m和 n,则遍历数组 nums1 需要 O(m) 的时间,判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间,因此总时间复杂度是O(mn)。
如果使用哈希集合存储元素,则可以在O(1) 的时间内判断一个元素是否在集合中,从而降低时间复杂度。
首先使用两个集合分别存储两个数组中的元素,然后遍历较小的集合,判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。
该方法的时间复杂度可以降低到 O(m+n)
代码:
class Solution {
public int [ ] intersection ( int [ ] nums1, int [ ] nums2) {
Set < Integer > set1 = new HashSet < Integer > ( ) ;
Set < Integer > set2 = new HashSet < Integer > ( ) ;
for ( int num : nums1) {
set1. add ( num) ;
}
for ( int num : nums2) {
set2. add ( num) ;
}
return getIntersection ( set1, set2) ;
}
public int [ ] getIntersection ( Set < Integer > set1, Set < Integer > set2) {
if ( set1. size ( ) > set2. size ( ) ) {
return getIntersection ( set2, set1) ;
}
Set < Integer > intersectionSet = new HashSet < Integer > ( ) ;
for ( int num : set1) {
if ( set2. contains ( num) ) {
intersectionSet. add ( num) ;
}
}
int [ ] intersection = new int [ intersectionSet. size ( ) ] ;
int index = 0 ;
for ( int num : intersectionSet) {
intersection[ index++ ] = num;
}
return intersection;
}
}
执行结果
通过
执行用时:4 ms,在所有 Java 提交中击败了21.31 % 的用户
内存消耗:38.7 MB,在所有 Java 提交中击败了28.49 % 的用户
复杂度分析
时间复杂度:O ( m+ n )
空间复杂度:O ( m+ n )
Java方法二:排序 + 双指针
如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序,然后使用两个指针遍历两个数组。
可以预见的是加入答案的数组的元素一定是递增的,为了保证加入元素的唯一性,我们需要额外记录变量 pre
表示上一次加入答案数组的元素。
初始时,两个指针分别指向两个数组的头部。每
次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,且该数字不等于pre
,将该数字添加到答案并更新 pre
变量,同时将两个指针都右移一位。
当至少有一个指针超出数组范围时,遍历结束。
代码
class Solution {
public int [ ] intersection ( int [ ] nums1, int [ ] nums2) {
Arrays. sort ( nums1) ;
Arrays. sort ( nums2) ;
int length1 = nums1. length, length2 = nums2. length;
int [ ] intersection = new int [ length1 + length2] ;
int index = 0 , index1 = 0 , index2 = 0 ;
while ( index1 < length1 && index2 < length2) {
int num1 = nums1[ index1] , num2 = nums2[ index2] ;
if ( num1 == num2) {
// 保证加入元素的唯一性
if ( index == 0 || num1 != intersection[ index - 1 ] ) {
intersection[ index++ ] = num1;
}
index1++ ;
index2++ ;
} else if ( num1 < num2) {
index1++ ;
} else {
index2++ ;
}
}
return Arrays. copyOfRange ( intersection, 0 , index) ;
}
}
执行结果
通过
执行用时:1 ms,在所有 Java 提交中击败了99.93 % 的用户
内存消耗:38.8 MB,在所有 Java 提交中击败了8.99 % 的用户
复杂度分析
时间复杂度:O ( mlogm + nlogn )
空间复杂度:O ( logm + logn )
💬总结
今天是力扣算法题打卡的第五十二天! 文章采用 C#
和 Java
两种编程语言进行解题 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们 那今天的算法题分享到此结束啦,明天再见!