【力扣-350打卡】

我不是女神ヾ 2023-09-26 16:29 67阅读 0赞

package com.example.demomain.demoleetcode.easy;
 
 import org.apache.commons.collections4.CollectionUtils;
 import org.junit.jupiter.api.Test;
 
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.stream.Collectors;
 
 /**
 * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2,2]
 * 
 * 示例 2:
 * 
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[4,9]
 * 
 * 
 * 
 * 提示：
 * 
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 1000
 *
 * @author lfsun
 */
 public class Intersect {
 
 /**
 * stream + org.apache.commons.collections4.CollectionUtils
 * 但是力扣不同意...error: package org.apache.commons.collections4 does not exist(已经是放到 begin 下面的)
 *
 * @param nums1
 * @param nums2
 * @return
 */
 public int[] intersectByStream(int[] nums1, int[] nums2) {
 
 List<Integer> collect1 = Arrays.stream(nums1).boxed().collect(Collectors.toList());
 List<Integer> collect2 = Arrays.stream(nums2).boxed().collect(Collectors.toList());
 return CollectionUtils.intersection(collect1, collect2).stream().mapToInt(Integer::valueOf).toArray();
 }
 
 /**
 * 由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。
 * 对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
 * 
 * 首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，
 * 然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，
 * 并减少哈希表中该数字出现的次数。
 * 
 * 为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
 *
 * @param nums1
 * @param nums2
 * @return
 */
 public int[] intersectByMap(int[] nums1, int[] nums2) {
 
 if (nums1.length > nums2.length) {
 
 return intersectByMap(nums2, nums1);
 }
 Map<Integer, Integer> map = new HashMap<>();
 for (int num : nums1) {
 
 int count = map.getOrDefault(num, 0) + 1;
 map.put(num, count);
 }
 int[] intersection = new int[nums1.length];
 int index = 0;
 for (int num : nums2) {
 
 int count = map.getOrDefault(num, 0);
 if (count > 0) {
 
 intersection[index++] = num;
 count--;
 if (count > 0) {
 
 map.put(num, count);
 } else {
 
 map.remove(num);
 }
 }
 }
 return Arrays.copyOfRange(intersection, 0, index);
 }
 
 /**
 * 排序 + 双指针
 * 如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
 * 
 * 首先对两个数组进行排序，然后使用两个指针遍历两个数组。
 * 
 * 初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
 *
 * @param nums1
 * @param nums2
 * @return
 */
 public int[] intersectBySortAndBin(int[] nums1, int[] nums2) {
 
 Arrays.sort(nums1);
 Arrays.sort(nums2);
 int aLen = nums1.length, bLen = nums2.length;
 int[] intersection = new int[Math.min(aLen, bLen)];
 int left = 0, right = 0, index = 0;
 while (left < aLen && right < bLen) {
 
 if (nums1[left] < nums2[right]) {
 
 left++;
 } else if (nums1[left] > nums2[right]) {
 
 right++;
 } else {
 
 intersection[index] = nums1[left];
 left++;
 right++;
 index++;
 }
 }
 return Arrays.copyOfRange(intersection, 0, index);
 }
 
 
 @Test
 public void test() {
 
 int[] nums1 = {
 1, 2, 2, 4, 5};
 int[] nums2 = {
 1, 2, 2, 5};
 int[] result = intersectByStream(nums1, nums2);
 for (int i : result) {
 
 System.out.println(i);
 }
 
 }
 }