[LintCode] Intersection of Two Arrays 两个数组相交

时间:2022-11-12 13:20:36

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

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

Have you met this question in a real interview?
Example

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Challenge

Can you implement it in three different algorithms?

LeetCode上的原题,请参见我之前的博客Intersection of Two Arrays

解法一:

class Solution {
public:
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s, res;
for (auto a : nums1) s.insert(a);
for (auto a : nums2) {
if (s.count(a)) res.insert(a);
}
return vector<int>(res.begin(), res.end());
}
};

解法二:

class Solution {
public:
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int i = , j = ;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] < nums2[j]) ++i;
else if (nums1[i] > nums2[j]) ++j;
else {
if (res.empty() || res.back() != nums1[i]) {
res.push_back(nums1[i]);
}
++i; ++j;
}
}
return res;
}
};

解法三:

class Solution {
public:
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> res;
sort(nums2.begin(), nums2.end());
for (auto a : nums1) {
if (binarySearch(nums2, a)) {
res.insert(a);
}
}
return vector<int> (res.begin(), res.end());
}
bool binarySearch(vector<int> &nums, int target) {
int left = , right = nums.size();
while (left < right) {
int mid = left + (right - left) / ;
if (nums[mid] == target) return true;
else if (nums[mid] < target) left = mid + ;
else right = mid;
}
return false;
}
};

解法四:

class Solution {
public:
/**
* @param nums1 an integer array
* @param nums2 an integer array
* @return an integer array
*/
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end()), res;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(res, res.begin()));
return vector<int>(res.begin(), res.end());
}
};

[LintCode] Intersection of Two Arrays 两个数组相交的更多相关文章

  1. &lbrack;LeetCode&rsqb; 349&period; Intersection of Two Arrays 两个数组相交

    Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1 ...

  2. &lbrack;LeetCode&rsqb; Intersection of Two Arrays 两个数组相交

    Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] ...

  3. 349 Intersection of Two Arrays 两个数组的交集

    给定两个数组,写一个函数来计算它们的交集.例子: 给定 num1= [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].提示:    每个在结果中的元素必定是唯一的.    我们 ...

  4. &lbrack;LeetCode&rsqb; 350&period; Intersection of Two Arrays II 两个数组相交II

    Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1 ...

  5. &lbrack;LintCode&rsqb; Intersection of Two Arrays II 两个数组相交之二

    Given two arrays, write a function to compute their intersection.Notice Each element in the result s ...

  6. &lbrack;LeetCode&rsqb; Intersection of Two Arrays II 两个数组相交之二

    Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] ...

  7. &lbrack;LeetCode&rsqb; 350&period; Intersection of Two Arrays II 两个数组相交之二

    Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1 ...

  8. LeetCode 4 Median of Two Sorted Arrays &lpar;两个数组的mid值&rpar;

    题目来源:https://leetcode.com/problems/median-of-two-sorted-arrays/ There are two sorted arrays nums1 an ...

  9. &lbrack;leetcode350&rsqb;Intersection of Two Arrays II求数组交集

    List<Integer> res = new ArrayList<>(); Arrays.sort(nums1); Arrays.sort(nums2); int i1 = ...

随机推荐

  1. ruby web性能响应时间

    可以统计单个web页面加载时间. require 'watir-webdriver' require 'watir-webdriver-performance' b = Watir::Browser. ...

  2. CTF---Web入门第一题 what a fuck&excl;这是什么鬼东西&quest;

    what a fuck!这是什么鬼东西?分值:10 来源: DUTCTF 难度:易 参与人数:7942人 Get Flag:3358人 答题人数:3475人 解题通过率:97% what a fuck ...

  3. Codeforces Round &num;441 &lpar;Div&period; 2&comma; by Moscow Team Olympiad&rpar; C&period; Classroom Watch

    http://codeforces.com/contest/876/problem/C 题意: 现在有一个数n,它是由一个数x加上x每一位的数字得到的,现在给出n,要求找出符合条件的每一个x. 思路: ...

  4. python的Web框架,auth权限系统

    使用django默认权限系统实现用户登录退出 判断用户是否登录 request.user.is_authenticated 返回的为bool值 一个简单的登录视图范式: # 导包 from djang ...

  5. Linux 基础教程 37-进程命令

    pidof     我们知道每个小孩一出生就会一个全国唯一的编号来对其进行标识,用于以后上学,办社保等,就是我们的身份证号.那么在Linux系统中,用来管理运行程序的标识叫做PID,就是大家熟知的进程 ...

  6. Java&lowbar;异常处理(Exception)

    异常:Exception try{ //捕获异常 }catch{ //处理异常 } 异常处理机制: 1.在try块中,如果捕获了异常,那么剩余的代码都不会执行,会直接跳到catch中, 2.在try之 ...

  7. 美国保健品品牌介绍之Now Foods

    Now Foods是美国著名的美国保健品品牌,定位于大众品牌. 美国Now Foods公司位于美国伊利诺州,*中文名叫健而婷,成立于1968年,是美国保健品市场上名列三甲的国际知名的天然保健品牌,其 ...

  8. 通用性能测试过程模型GAME(A)

    1.3.1  Goal(定义目标) 制定一个明确而详细的测试目标是性能测试开始的第一步,也是性能测试成功的关键. 本步骤的开始时间:需求获取阶段 本步骤的输入:性能需求意向 本步骤的输出:明确的性能测 ...

  9. redis之(十九)redis的管理

    [一]redis的安全 --->redis的简洁美,使得redis的安全设计是在“redis运行在可信环境”这个前提下做出来,. --->在生产环境运行时不能允许外界直接链接到redis, ...

  10. Linux中history历史命令使用方法详解

    当你在玩Linux的时候,如果你经常使用命令行来控制你的Linux系统,那么有效地使用命令历史机制将会使效率获得极大提升.事实上,一旦你掌 握了我在下面给出的15个有关Linux history历史命 ...