查找两个整型数组的公共元素

简介:

一,问题描述

给定两个整型数组,假设一个长度为M,另一个长度为N。请找出(打印出)这两个数组中的公共元素。

 

二,算法分析

有两种思路求解这个问题。

①使用一个HashSet保存第一个数组中的所有元素,然后遍历第二个数组中的每个元素,判断该元素是否在HashSet中。如果在,就表明这个元素是公共元素。

此方法的时间复杂度为O(M+N),空间复杂度为O(M)[假设第一个数组长度为M,保存在HashSet中]。

 

②首先对两个数组进行排序。然后分别设置两个指针 i, j   初始时,分别指向两个数组的第一个元素,依次比较这两个指针指向的元素,指向较小的元素的那个指针向后移一位。如果,两个元素相同,则两个指针同时向后移一位。

此方法,首先需要对数组排序,时间复杂度为O(MlogM + NlogN),空间复杂度为O(1)---不考虑排序算法的空间复杂度。

 

三,完整代码实现

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class CommonElement {
    
    //排序时间复杂度为O(NlogN+MlogM),排序之后寻找公共元素的时间复杂度为O(M+N)
    public static void printCommonEle(int[] arr1, int[] arr2){
        if(arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0)
            return;
        
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        int i = 0, j = 0;
        while(i < arr1.length && j < arr2.length)
        {
            if(arr1[i] > arr2[j])
                j++;
            else if(arr1[i] < arr2[j])
                i++;
            else{
                System.out.print(arr1[i] + " ");
                i++;
                j++;
            }
        }
    }
    
    //时间复杂度为O(M),空间复杂度为O(N)
    public static void findCommon(int[] arr1, int[] arr2){
        if(arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0)
            return;
        
        Set<Integer> intSets = new HashSet<Integer>();
        
        for (int i : arr1)
            intSets.add(i);
        
        for(int i : arr2)
            if(intSets.contains(i))
                System.out.print(i + " ");
    }
    
    public static void main(String[] args) {
        int[] arr1 = {3,5,1,7,8};
        int[] arr2 = {4,7,3,8,5,2,9,0};

        printCommonEle(arr1, arr2);
        System.out.println();
        findCommon(arr1, arr2);
    }
}
View Code

本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5742897.html,如需转载请自行联系原作者
相关文章
|
13天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
5天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
12天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
8天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
769 23
|
7天前
|
人工智能 Java Nacos
基于 Spring AI Alibaba + Nacos 的分布式 Multi-Agent 构建指南
本文将针对 Spring AI Alibaba + Nacos 的分布式多智能体构建方案展开介绍,同时结合 Demo 说明快速开发方法与实际效果。
495 37
|
7天前
|
机器学习/深度学习 人工智能 搜索推荐
万字长文深度解析最新Deep Research技术:前沿架构、核心技术与未来展望
近期发生了什么自 2025 年 2 月 OpenAI 正式发布Deep Research以来,深度研究/深度搜索(Deep Research / Deep Search)正在成为信息检索与知识工作的全新范式:系统以多步推理驱动大规模联网检索、跨源证据。
476 41
|
1天前
|
文字识别 监控 物联网
这是我写的实施一地两检的跨境高铁站旅客资料预报系统的系统架构
本文设计了一套基于IAPIS理念的高铁跨境旅客预报与边检联动系统,覆盖青青草原内地与喜羊羊特别行政区间“一地两检”场景。系统在旅客购票后即采集证件、生物特征及行程信息,通过Advance Passenger Info Checker等模块,向出发地和目的地移民管理机构实时推送数据,实现出入境许可预审。支持线上/线下购票、检票、退票全流程管控,结合面部识别、行为追踪技术监控旅客状态,防止滞留或非法通行。列车发车前进行最终核验,确保所有跨境旅客获边检许可。若旅行被中途取消,系统自动改签、退票并通知各方,保障安全与效率。(239字)