文档章节

两数组的交集(无重复)Intersection of Two Arrays

叶枫啦啦
 叶枫啦啦
发布于 2017/06/20 16:43
字数 330
阅读 3
收藏 0

问题:

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

解决:

①使用hashSet保存nums1数组中的值,然后比较即可。耗时5ms.

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int n : nums1) {
            set.add(n);
        }
        for (int n : nums2) {
            if (set.contains(n)) {
                list.add(n);
                set.remove(n);
            }
        }
        int res[] = new int[list.size()];
        for(int i = 0;i < list.size();i ++ ){
            res[i] = list.get(i);
        }
        return res;
    }
}

②使用双指针法, 使用一个临时数组保存相同的数值,当扫描时存在与临时数组最后一个值相同的数时,跳过,否则,添加到临时数组中。

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return new int[0];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int temp[] = new int[nums1.length];
        int p1 = 0;
        int p2 = 0;
        int p = 0;
        while(p1 < nums1.length && p2 < nums2.length){
            if (nums1[p1] == nums2[p2]) {
                if (p - 1 >= 0 && temp[p - 1] == nums1[p1]) {//相同的值重复
                    //什么都不做
                }else{
                    temp[p] = nums1[p1];
                    p ++;
                }
                p1 ++;
                p2 ++;
            }else if (nums1[p1] < nums2[p2]) {
                p1 ++;
            }else{
                p2 ++;
            }
        }
        int res[] = new int[p];
        for (int i = 0;i < p ;i ++ ) {
            res[i] = temp[i];
        }

        return res;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
Leetcode PHP题解--D118 350. Intersection of Two Arrays II

D118 350. Intersection of Two Arrays II 题目链接 350. Intersection of Two Arrays II 题目分析 返回给定两个数组的交集。 思路 从数量较多的那个数组开始去另一个数组寻找是否元素存在,...

skys215
前天
4
0
【Leetcode】【简单】【350. 两个数组的交集 II】【JavaScript】

题目描述 350. 两个数组的交集 II 给定两个数组,编写一个函数来计算它们的交集。 示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例 2: 输入: nums1 = [4,9,5], nums2 = [9...

孙达
09/06
0
0
LeetCode算法题-Intersection of Two Arrays(Java实现-四种解法)

这是悦乐书的第207次更新,第219篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第75题(顺位题号是349)。给定两个数组,编写一个函数来计算它们的交集。例如: 输入:nums1...

小川94
2018/12/20
0
0
LeetCode算法题-Intersection of Two Arrays II(Java实现)

这是悦乐书的第208次更新,第220篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第76题(顺位题号是350)。给定两个数组,编写一个函数来计算它们的交集。例如: 输入:nums1...

小川94
2018/12/21
0
0
每周一练 之 数据结构与算法(Set)

这是第四周的练习题,五一放假结束,该收拾好状态啦。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据结构与算法(LinkedList) 3.每周一练 之 数据结构...

pingan8787
05/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JS其他类型值转化为Boolean类型规则

本文转载于:专业的前端网站➤JS其他类型值转化为Boolean类型规则 由于最近在笔试的时候,发现好多关于其他类型转化为Boolean类型的题目,因此总结一下! 一、String类型转化为Boolean 1.转化...

前端老手
11分钟前
2
0
EurekaClient自动装配及启动流程解析

在上篇文章中,我们简单介绍了EurekaServer自动装配及启动流程解析,本篇文章则继续研究EurekaClient的相关代码 老规矩,先看spring.factories文件,其中引入了一个配置类EurekaDiscoveryClie...

Java学习录
17分钟前
2
0
析构函数是否必须为虚函数?为何?

在C++中,基类指针可以指向一个派生类的对象。如果基类的析构函数不是虚函数,当需要delete这个指向派生类的基类指针时,就只会调用基类的析构函数,而派生类的析构函数无法被调用。容易造成...

天王盖地虎626
17分钟前
2
0
【TencentOS tiny】深度源码分析(7)——事件

引言 大家在裸机编程中很可能经常用到flag这种变量,用来标志一下某个事件的发生,然后在循环中判断这些标志是否发生,如果是等待多个事件的话,还可能会if((xxx_flag)&&(xxx_flag))这样子做...

杰杰1号
21分钟前
2
0
聊聊nacos client的ServerHttpAgent

序 本文主要研究一下nacos client的ServerHttpAgent HttpAgent nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/http/HttpAgent.java public interface HttpAgent { ......

go4it
27分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部