求两个数组的交集

桃扇骨 2022-03-08 03:26 258阅读 0赞

方法一：使用一个Map将其中一个数组放到map中，循环遍历第二个数组，如果map中存在第二个数组中含有的的值，放到结果集中.时间复杂度O(n) ，空间复杂度O(n)

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    public class TwoArray {
    	
    	public static void main(String[] args) {
    		int [] nums1={1,3,5,6,4,7,9,11,13};
    		int [] nums2 = {1,9,8,6};
    		List<Integer> list = new ArrayList<Integer>();
    		Map<Integer,Integer> map  = new HashMap<Integer,Integer>();
    		for(int i = 0;i<nums1.length;i++){
    			map.put(nums1[i], i);
    		}
    		
    		for(int i = 0;i<nums2.length;i++){
    			if(map.containsKey(nums2[i])){
    				list.add(nums2[i]);
    			}
    		}
    		System.out.println(list);
    	}
    }

第二种：先排序，然后定义两个指针，时间复杂度O(nlogn) (排序)，空间复杂度O(1)

public ArrayList<Integer> getIntersection2(int[] arr, int[] arr2) {
    		
    		ArrayList<Integer> res = new ArrayList<Integer>();
    		if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {
    			return res;
    		}
    		
    		Arrays.sort(arr);
    		Arrays.sort(arr2);
    		int i = 0;
    		int j = 0;
    		while(i < arr.length && j < arr2.length) {
    			if(arr[i] < arr2[j]) {
    				i ++;
    			}
    			else if(arr[i] > arr2[j]) {
    				j ++;
    			}
    			else {
    				if(!res.contains(arr[i])) {
    					res.add(arr[i]);
    				}
    				i ++;
    				j ++;
    			}
    		}
    		return res;
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，258人围观）

还没有评论，来说两句吧...

相关阅读

相关 349. 两个数组的交集

349. 两个数组的交集题干背景易错点代码实现题干背景 [力扣入口-349. 两个数组的交集][-349.] 题意：给定两个数组，编写

雨点打透心脏的1/2处/ 2024年03月17日 21:17/ 0 赞/ 82 阅读

相关 leetcode 349. 两个数组的交集

题目链接：[349. 两个数组的交集][349.] 给定两个数组，编写一个函数来计算它们的交集。示例 1：输入：nums1 = [1,2,2,1], nums

骑猪看日落/ 2022年12月13日 10:00/ 0 赞/ 183 阅读

相关排序----349. 两个数组的交集I &&350. 两个数组的交集II

349 【题目】给定两个数组，编写一个函数来计算它们的交集。【示例】输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\] 输出

ゞ浴缸里的玫瑰/ 2022年11月16日 10:48/ 0 赞/ 185 阅读

相关 350. 两个数组的交集 II

> 给定两个数组，编写一个函数来计算它们的交集。 > > > > 示例 1： > > 输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]

迈不过友情╰/ 2022年10月18日 04:59/ 0 赞/ 173 阅读

相关求两个数组的交集 ->可以使用HashMap做

求两个数组的交集思路： 1，第一个数组的元素放入hashmap中，令值为1（不论是否重复）. 2. 循环检验第二个数组的元素，判断hashmap中是否已经存在该值（m.

ゞ浴缸里的玫瑰/ 2022年09月25日 03:21/ 0 赞/ 163 阅读

相关 leetcode 349 两个数组的交集

前言题目：[349. 两个数组的交集][349.] 参考答案：[349. 两个数组的交集-力扣官方题解][349. _-] --------------------

r囧r小猫/ 2022年09月09日 04:35/ 0 赞/ 147 阅读

相关 350. 两个数组的交集 II

[https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/submissions/][https_leet

冷不防/ 2022年09月07日 01:23/ 0 赞/ 183 阅读

相关求两个数组的交集

方法一：使用一个Map将其中一个数组放到map中，循环遍历第二个数组，如果map中存在第二个数组中含有的的值，放到结果集中.时间复杂度O(n) ，空间复杂度O(n)

桃扇骨/ 2022年03月08日 03:26/ 0 赞/ 259 阅读

相关 LeetCode：两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出:

蔚落/ 2021年11月22日 03:08/ 0 赞/ 284 阅读

相关 LeetCode---349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示

比眉伴天荒/ 2021年09月23日 22:26/ 0 赞/ 306 阅读