LeetCode_349. 两个数组的交集

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 
 * 
 * @ClassName: Solution
 * 
 * @Description: 给定两个数组，编写一个函数来计算它们的交集。
 * 
 *               输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
 * @author: Mr.Yang
 * 
 * @date: 2020年2月9日 下午3:39:28
 */
public class Solution {

	public int[] intersection(int[] nums1, int[] nums2) {
		// 保存目标元素的集合
		List<Integer> targetList = new ArrayList<>();

		// set 元素不重复 ，存放数组1
		Set<Integer> set = new TreeSet<>();
		for (int num : nums1) {
			set.add(num);
		}

		// 遍历数组2，判断是数组2中的每个元素是否在数组1中
		// 存在则加入到targetList
		// 同时为了防止数组2有重复的数据，导致targetList重复，所以要移除set中的元素，防止重复
		for (int num2 : nums2) {
			if (set.contains(num2)) {
				targetList.add(num2);
				set.remove(num2);
			}
		}

		// list转数组
		int[] target = new int[targetList.size()];
		for (int i = 0; i < target.length; i++) {
			target[i] = targetList.get(i);
		}
		return target;
	}

	public static void main(String[] args) {
		Solution solution = new Solution();
		int[] target = solution.intersection(new int[] { 1, 2, 2, 1 }, new int[] { 2, 2 });
		for (int i = 0; i < target.length; i++) {
			System.out.println(target[i] + ",");
		}
	}
}

public int[] intersection3(int[] nums1, int[] nums2) {
		// 数组1 入set
		HashSet<Integer> set1 = new HashSet<Integer>();
		for (Integer n : nums1) {
			set1.add(n);
		}
		// 数组2 入set
		HashSet<Integer> set2 = new HashSet<Integer>();
		for (Integer n : nums2) {
			set2.add(n);
		}

		// 比较
		if (set1.size() < set2.size()) {
			return setIntersection(set1, set2);
		} else {
			return setIntersection(set2, set1);
		}
	}

	/**
	 * 
	 * 
	 * @Title: setIntersection
	 * 
	 * @Description: 迭代较小的集合检查是否存在在较大集合中 减少遍历次数
	 * 
	 * @param smallSet
	 * @param largeSet
	 * 
	 * @return: int[]
	 */
	private int[] setIntersection(HashSet<Integer> smallSet, HashSet<Integer> largeSet) {
		int[] target = new int[smallSet.size()]; // 先开辟一个小的内存区域
		int idx = 0;// 下面的这种遍历，没有下标，定义一个索引下标
		for (int num : smallSet) {// 迭代较小的集合检查是否存在在较大集合中 减少遍历次数
			if (largeSet.contains(num)) {
				// target[idx] = num;
				// idx++;
				// 上面两行可以直接写成如下
				target[idx++] = num;
			}
		}
		return Arrays.copyOf(target, idx); // 返回idx长度的数组，避免出现多余的0
	}

public int[] intersection(int[] nums1, int[] nums2) {
		// 数组1 入set
		HashSet<Integer> set1 = new HashSet<Integer>();
		for (Integer n : nums1)
			set1.add(n);
		// 数组2 入set
		HashSet<Integer> set2 = new HashSet<Integer>();
		for (Integer n : nums2)
			set2.add(n);

		// 内置函数
		set1.retainAll(set2);

		// set转数组
		int[] output = new int[set1.size()];
		int idx = 0;
		for (int s : set1)
			output[idx++] = s;
		return output;
	}