有效的算法，以确定是否两组数字是不相交的 [英] Efficient algorithm to determine if two sets of numbers are disjoint

问题描述

练了软件开发人员的访谈和卡住了一个算法问题。

 由于两套无序整数与长度为M和其他的阵列
长度为n以及其中M＆LT; Ñ​​找到一种有效的算法，以确定是否
集是不相交的。我发现在O（nm）的时间的解决方案，但还没有
发现任何比这种更有效的，如在O（N日志米）的时间。
 

解决方案

使用数据结构，有O（1）查找/插入您可以轻松地插入第一组中的所有元素。

在第二盘之后的foreach元素，如果存在不相交，否则不相交

伪code

 函数isDisjoint（List1中，list2中）
    HashMap的=新的HashMap（）;
    的foreach（X List1中）
        HashMap.put（X，真）;

    的foreach（Y在list2中）
        如果（HashMap.hasKey（y））为
             返回false;
    返回true;
 

这会给你一个O（N + M）的解决方案。

Practicing for software developer interviews and got stuck on an algorithm question.

Given two sets of unsorted integers with array of length m and other of 
length n and where m < n find an efficient algorithm to determine if 
the sets are disjoint. I've found solutions in O(nm) time, but haven't 
found any that are more efficient than this, such as in O(n log m) time.

解决方案

Using a datastructure that has O(1) lookup/insertion you can easily insert all elements of first set.

Then foreach element in second set, if it exists not disjoint, otherwise it is disjoint

Pseudocode

function isDisjoint(list1, list2)
    HashMap = new HashMap();
    foreach( x in list1)
        HashMap.put(x, true);

    foreach(y in list2)
        if(HashMap.hasKey(y))
             return false;
    return true;

This will give you an O(n + m) solution

这篇关于有效的算法，以确定是否两组数字是不相交的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！