凌美上海建设工程网站,德州王霞网站建设,公司网站怎么建站,wordpress win 伪静态❓349. 两个数组的交集
难度#xff1a;简单
给定两个数组 nums1 和 nums2 #xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1#xff1a; 输入#xff1a;nums1 [1,2,2,1], nums2 [2,2] 输出#xff1a;[…❓349. 两个数组的交集
难度简单
给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1 输入nums1 [1,2,2,1], nums2 [2,2] 输出[2] 示例 2 输入nums1 [4,9,5], nums2 [9,4,9,8,4] 输出[9,4] 解释[4,9] 也是可通过的 提示
1 nums1.length, nums2.length 10000 nums1[i], nums2[i] 1000
思路
法一排序双指针
如果两个数组是有序的则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的为了保证加入元素的唯一性我们在向结果数组ans 添加元素时要判断该元素是否已经存在如果ans添加第一个元素时不需要判断。
法二哈希表
输出结果中的每个元素一定是唯一的也就是说输出的结果的去重的根据哈希表的性质可以去重
首先将 num1 中的元素放到哈希表 s1 中然后遍历 num2 中元素如果 s1 中也存在则保存到另一个哈希表 ans 中;最后哈希表 ans 就是所求交集将结果集合转为数组。
代码(Java、C)
法一排序双指针 Java
class Solution {public int[] intersection(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int len1 nums1.length, len2 nums2.length;int[] ans new int[Math.min(len1, len2)];int index1 0, index2 0, index 0;while(index1 len1 index2 len2){if(nums1[index1] nums2[index2]){if(index 0){ans[index] nums1[index1];}else if(nums1[index1] ! ans[index - 1]){ans[index] nums1[index1];}index1;index2;}else if(nums1[index1] nums2[index2]){index1;}else{index2;}}return Arrays.copyOfRange(ans, 0, index);}
}C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());vectorint ans;vectorint::iterator ite1 nums1.begin(), ite2 nums2.begin();while(ite1 ! nums1.end() ite2 ! nums2.end()){if(*ite1 *ite2){if(ans.size() 0){ans.push_back(*ite1);}else if(*ite1 ! ans.back()){ans.push_back(*ite1);}ite1;ite2;}else if(*ite1 *ite2){ite1;}else{ite2;}}return ans;}
};法二哈希表 Java
class Solution {public int[] intersection(int[] nums1, int[] nums2) {SetInteger s1 new HashSetInteger();SetInteger ans new HashSetInteger();for(int num : nums1){s1.add(num);}for(int num: nums2){if(s1.contains(num)){ans.add(num);}}//将结果集合转为数组, 另外申请一个数组存放setRes中的元素,最后返回数组int[] arr new int[ans.size()];int j 0;for(int i : ans){arr[j] i;}return arr;}
}C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint s(nums1.begin(), nums1.end());unordered_setint ans;for(int num : nums2){if(s.find(num) ! s.end()){ans.insert(num);}}return vectorint(ans.begin(), ans.end());;}
};运行结果 复杂度分析
时间复杂度法一 O ( m l o g m n l o g n ) O(m \ log mn \ log n) O(m logmn logn)其中 m 和 n 分别是两个数组的长度。对两个数组排序的时间复杂度分别是 O ( m log m ) O(m \log m) O(mlogm) 和 O ( n log n ) O(n \log n) O(nlogn)双指针寻找交集元素的时间复杂度是 O ( m n ) O(mn) O(mn)。法二为 O ( m n ) O(m n) O(mn)。空间复杂度法一 O ( l o g m l o g n ) O( log m log n) O(logmlogn)其中 m 和 n 分别是两个数组的长度 , 空间复杂度主要取决于排序使用的额外空间。法二为 O ( n ) O(n) O(n) n 为两数组长度的最小值。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
