在两个未排序的数组中查找公共元素

Question

我试图找到这个问题的解决方案:我有两个整数A和B(A和B可以有不同的维度).我必须在这两个数组中找到共同的元素.我有另一个条件:公共元素之间的最大距离是k.所以,这是我的解决方案.我认为是正确的:

for (int i = 0; i<A.length; i++){
    for (int j=jlimit; (j<B.length) && (j <= ks); j++){
        if(A[i]==B[j]){
            System.out.println(B[j]);
            jlimit = j;
            ks = j+k;
        }//end if
    }
}

有没有办法做出更好的解决方案？有什么建议？提前致谢!

Answer 1

根据你的解释,我认为最直接的方法是读取数组A,将所有元素放在Set(setA)中,对B(setB)执行相同操作,并使用该retainAll方法查找两个集合的交集(属于两者的项目)的集合).

您将看到k distance根本没有使用它,但我认为无法使用导致代码更快或更可维护的条件.我提倡的解决方案在不强制执行该条件的情况下工作,因此当条件为真时(即称为"弱化前置条件"),它也可以工作

Answer 2

实施二进制搜索和快速排序!

这将导致大量的代码....但最快的结果.

您可以使用快速排序来排序较大数组的元素,这将导致O(nlogn).

然后为每个值迭代较小的数组,并对另一个数组中的特定元素进行二进制搜索.在二进制搜索中为距离添加一些逻辑.

我认为你可以将复杂性降低到O(nlogn).最坏情况O(n ^ 2)

伪代码.

larger array equals a
other array equals b

sort a

iterate through b
       binary search b at iterated index
     // I would throw (last index - index) logic in binary search
     // to exit out of that even faster by returning "NOT FOUND" as soon as that is hit.
       if found && (last index - index) is less than or equal 
          store last index
          print value

这是我认为最快的方法来解决你的问题.

Answer 3

尽管这可能是一个骗局，但由于它使用HashSets，因此对于该算法的 Java 实现来说非常好。如果您需要该算法的伪代码，请不要继续阅读。

JavaDoc 中的来源和作者。干杯。

/**
 * @author Crunchify.com
 */
public class CrunchifyIntersection {

    public static void main(String[] args) {
         Integer[ ] arrayOne = { 1, 4, 5, 2, 7, 3, 9 };
         Integer[ ] arrayTwo = { 5, 2, 4, 9, 5 };

         Integer[ ] common = iCrunchIntersection.findCommon( arrayOne, arrayTwo );

         System.out.print( "Common Elements Between Two Arrays: " );       
         for( Integer entry : common ) {
              System.out.print( entry + " " );
         }
   }

   public static Integer[ ] findCommon( Integer[ ] arrayOne, Integer[ ] arrayTwo ) {

        Integer[ ] arrayToHash;
        Integer[ ] arrayToSearch;

        if( arrayOne.length < arrayTwo.length ) {
            arrayToHash = arrayOne;
            arrayToSearch = arrayTwo;
        } else {
            arrayToHash = arrayTwo;
            arrayToSearch = arrayOne;
        }

        HashSet<Integer> intersection = new HashSet<Integer>( );

        HashSet<Integer> hashedArray = new HashSet<Integer>( );
        for( Integer entry : arrayToHash ) {
            hashedArray.add( entry );
        }

        for( Integer entry : arrayToSearch ) {
            if( hashedArray.contains( entry ) ) {
                intersection.add( entry );
            }
        }

        return intersection.toArray( new Integer[ 0 ] );
    }
 }