首页 > 其他分享 >LeetCode | 349 Intersection Of Two Arrays

LeetCode | 349 Intersection Of Two Arrays

时间:2024-08-09 11:40:10浏览次数:13  
标签:index Arrays Two public int 数组 Intersection nums1 nums2

分析

两个数组的交集,双指针使用的前提是,两个数组已经处于有序状态。双指针的本质是遍历;双指针在线性数据结构中,进行数据处理,每次只专注于两个元素;指针遍历将问题拆解为两部分,即已解决和待解决问题。倘若两个数组是无序的状态,双指针指向每次都无法确认是否在历史中已经出现过,这个时候其实就是双层for循环。

  • 排序
  • 双指针移动,任意一个移动到末尾需要直接停止
  • 去重判断
  • 移除结果数组末端的0

HashSet,哈希在寻找唯一性上有独特的优势,再加上Set的性质,相对于双指针方式,就像是在作弊一样。天然存在了去重和唯一性。

  • 将其中一个数组放进HashSet中,即完成了去重操作
  • 另一个数组中逐个遍历找到重叠的部分
  • 用ArrayList存储于HashSet中重叠的部分数据

主类

package com.github.dolphinmind.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author dolphinmind
 * @ClassName intersectionoftwoarrays
 * @description 349 求两个数组的交集
 * @date 2024/8/9
 */

public class InterSectionOfTwoArrays {

    /**
     * 双指针写法
     * @param nums1
     * @param nums2
     */
    public void intersectionTwoPointers(int[] nums1, int[] nums2) {

        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            System.out.println("数组为空");
            return;
        }

        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int len = Math.min(nums1.length, nums2.length);
        int[] res = new int[len];

        int i = 0, j = 0, index = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                /**
                 * 避免重复
                 * 首次添加元素:如果index == 0,说明结果数组还没有任何元素,此时直接将找到的交集元素添加到结果数组中
                 * 避免重复添加:如果index != 0, 说明结果数组中已经有至少一个元素。此时需要检查当前要添加的元素是否与结果数组中的最后一个元素相同
                 * 如果相同,则跳过本次循环,继续下一次循环,直到找到不同的元素
                 */
                if (index == 0 || res[index - 1] != nums1[i]) {
                    res[index++] = nums1[i];
                }
                i++;
                j++;
            }
        }

        printArray(removeZeros(res, index));
    }

    /**
     * 去除数组中0
     * @param arr
     * @param index
     * @return
     */
    public int[]  removeZeros(int[] arr, int index) {
        int[] newArr = new int[index];

        for (int i = 0; i < index; i++) {
            newArr[i] = arr[i];
        }

        return newArr;
    }
    public void printArray(int[] arr) {
        System.out.print("[");
        for (int item : arr) {
            System.out.print(item + " ");
        }
        System.out.println("]");
        System.out.println();
    }

    /**
     * HashSet写法
     */

    public void interSectionHashSet(int[] arr1, int[] arr2) {
        HashSet<Integer> set = new HashSet<>();
        List<Integer> res = new ArrayList<>();

        for (int item : arr1) {
            set.add(item);
        }

        for (int item : arr2) {
            if (set.contains(item)) {
                res.add(item);
            }
        }

        /**
         * 将List转换为数组.尽管mapToInt并没有改变流中的元素,但是它的作用是将Stream转换为IntStream
         * 以便最后能够直接使用.toArray()方法得到一个int[]类型
         */
        printArray(res.stream().mapToInt(x -> x).toArray());
    }

}


测试类

package com.github.dolphinmind.hashcode;

import com.github.dolphinmind.hash.InterSectionOfTwoArrays;
import org.junit.Test;

/**
 * @author dolphinmind
 * @ClassName InterSectionOfTwoArraysTest
 * @description
 * @date 2024/8/9
 */

public class InterSectionOfTwoArraysTest {

    @Test
    public void test_intersection() {
        int[] nums1 = {};
        int[] nums2 = {3,4,5,6,7,8};

        new InterSectionOfTwoArrays().intersectionTwoPointers(nums1, nums2);
    }

    @Test
    public void test_interSectionHashSet() {
        int[] nums1 = {1,2,3,4,5,6,7,8};
        int[] nums2 = {3,4,5,6,7,8};
        new InterSectionOfTwoArrays().interSectionHashSet(nums1, nums2);
    }

}

标签:index,Arrays,Two,public,int,数组,Intersection,nums1,nums2
From: https://www.cnblogs.com/dolphinmind/p/18350494

相关文章

  • 使用QNetworkAccessManager实现FTP上传下载功能
    自己写了一份FTP的代码,可以上传下载单文件,上传下载多文件,上传目录所有文件,但是下载目录的功能有问题,接口里代码规范也没做(如果有大佬提供修改方案就更好了),代码直接复制可用,留给有需要的人。#pragmaonce#include<QObject>#include<QNetworkReply>#include<QNetworkAcce......
  • C. Even Subarrays
    原题链接题解这题用到的知识点很多,思维+前缀异或+容斥原理。1、题目告诉我们要找被除数个数是偶数个的异或和,那么什么数的被除数有偶数个?答案:非完全平方数。2、非完全平方数太多了,不好求。而我们又知道所有序列个数为(n+1)*n/2所以我们只要求出序列异或和为完全平方数......
  • Number of k-good subarrays
    我们发现,如果我们将满足题意的点在数轴上标出,那么我们可以获得若干个连续段。对于一个长度为\(l\)的连续段,他对答案的贡献就是\(\frac{l(l+1)}{2}\),我们把所有连续段的贡献加起来就得到了答案于是我们发现这个可以拆分成子问题,具体见这篇题解。\(sol(n-mx,k-1)\)就是拆分成的子问......
  • Gartner 魔力象限:单一供应商安全访问服务边缘 2024,Palo Alto Networks 再次荣膺领导者
    GartnerMagicQuadrantforSingle-VendorSASE2024Gartner魔力象限:单一供应商安全访问服务边缘2024请访问原文链接:https://sysin.org/blog/gartner-magic-quadrant-single-vendor-sase-2024/,查看最新版。原创作品,转载请保留出处。Gartner魔力象限:单一供应商SASE2024Pu......
  • 01-network-manager-all.yaml和interfaces和resolv.conf各有什么区别和联系
    01-network-manager-all.yaml、interfaces和resolv.conf是与网络配置相关的文件,它们在网络设置中有着不同的作用和使用方式。01-network-manager-all.yaml:这是一个配置文件,通常在Ubuntu系统上使用NetworkManager进行网络管理时使用。文件路径通常是/etc/netplan/01-net......
  • Python面试题:结合Python技术,如何使用NetworkX进行复杂网络建模与分析
    NetworkX是一个用于创建、操作和研究复杂网络(图)的Python库。它提供了丰富的工具来构建、操纵和分析各种类型的图。下面是一个基本的示例,演示如何使用NetworkX进行复杂网络建模与分析。安装NetworkX首先,确保你已经安装了NetworkX。可以使用以下命令进行安装:pipinstallne......
  • LeetCode | 160 Intersection of two linkedlists
    https://github.com/dolphinmind/datastructure/tree/datastructure-linkedlist分析判断两个链表是否相交,转换成了双指针相遇的问题。还是那句话,双指针的本质是遍历,走的路其实一样/***解决两个链接不相交而陷入无限循环的情况*初......
  • SDN(Software-Defined Networking,软件定义网络),NFV(Network Functions Virtualization,网
    目录SDN(Software-DefinedNetworking,软件定义网络)NFV(NetworkFunctionsVirtualization,网络功能虚拟化)SDN(软件定义网络)NFV(网络功能虚拟化)SDN的优势NFV的优势DC(数据中心)网关与MEC(移动边缘计算)节点DC网关MEC节点DC网关与MEC节点的协同作用SDN(Software-DefinedNet......
  • CIFAR-10 Implementing a Convolutional Neural Network
    Coding Assignment 4: Implementing aConvolutional Neural Network for CIFAR-10using KerasJuly 28, 20241 OverviewInthisassignment,youwillimplement a Convolutional Neural Network (CNN) to classify images from the CIFAR-10 dataset......
  • 深入解析与实战:解决 npm ERR! network ‘proxy‘ 配置问题
    在日常的前端开发工作中,使用npm(NodePackageManager)进行依赖管理已经成为了常态。然而,在某些情况下,我们可能会遇到网络配置问题导致的错误信息,比如npmERR!network'proxy'configissetproperly。本文将详细介绍如何解决这一问题,并通过实际案例演示正确的配置方法。......