Java在集合中查找公共元素

I need to find common elements in a collection of arrays using

我需要在使用的数组集合中找到共同的元素

public Comparable[] findCommonElements(Object[] collection)

as the signature of my algorithm, it should accept a collection of arrays (of varying length and of any type) as input, and be no greater than O(knlogn).

作为我的算法的签名，它应该接受一组数组（不同长度和任何类型）作为输入，并且不大于O（knlogn）。

I want to do a quick sort (??) of the arrays then do a binary search for the common elements. This should put me right at O(knlogn), but I'm not 100% sure about efficiency.

我想对数组进行快速排序（??）然后对公共元素进行二进制搜索。这应该让我在O（knlogn），但我不是100％肯定效率。

I'm lost on how to get the binary search to search the collections and then print the common elements. I am aware I cannot call common from a static method, but I left it to give an idea of what I tried. I am aware my time would be better spent learning how to use array lists and hash sets, but I am supposed to use concepts already covered, and these have not been.

我迷失了如何让二进制搜索来搜索集合然后打印常见元素。我知道我不能用静态方法调用common，但是我把它留给了我试过的东西。我知道我的时间会更好地学习如何使用数组列表和哈希集，但我应该使用已经涵盖的概念，但这些都没有。

Code:

public class CommonElements2<T extends Comparable<T>>
{
   Comparable[] tempArr;
   Comparable[] queryArray;
   Comparable[] common = new Comparable[queryArray.length];
   int counter = 0;
/* 
sort algorithm goes here
*/   
   public Comparable[] findCommonElements(Object[] collections)
   {
      queryArray = ((Comparable[])collections[0]);
      boolean found = false;

      for(int x = 0; x < queryArray.length; ++x)
      {
         for(int y = 1; y < collections.length; ++y)
         {
            tempArr = (Comparable[])collections[y];
            found = binarySearch(tempArr, 0, tempArr.length, queryArray[x]);

            if(!found)
            {
               break;
            }
            if(found)
            {
               common[counter] = queryArray[x];
               ++counter;
            }  
         } //end y for loop
      } // end x for loop
      return common;      
   } // end findCommonElements

   public boolean binarySearch(Comparable[] arr, int first, int last, Object searchItem)
   {
      boolean found;
      int mid = (first + (last - first)) /2;

      if(first > last)
         return false;

      int value = ((Comparable)searchItem).compareTo(arr[mid]);

      if(value < 0)
         value = -1;

      switch(value)
      {
         case 0:
            found = true;
            break;
         case -1:
            found = binarySearch(arr, first, mid - 1, searchItem);
            break;
         default:
            found = binarySearch(arr, mid + 1, last, searchItem);
            break;
      }
      return found;
   } //end bianry search

   public static void main(String[] args)
   {
        Object [] collections = new Object[4];
        collections[0] = new Integer[]{3, 4, 9, 8, 12, 15, 7, 13};
    collections[1] = new Integer[]{15,24,50,12,3,9};
    collections[2] = new Integer[]{78,65,24,13,9,3,12};
    collections[3] = new Integer[]{15,78,14,3,2,9,44,12};

        CommonElements2<Integer> one = new CommonElements2<Integer>();
        System.out.println(one.findCommonElements(collections));

   }
} // end class

Thank you for any help and input!

感谢您的帮助和意见！

1 个解决方案

#1

From my comment, here's an algorithm that can fulfill your work:

从我的评论，这是一个可以完成你的工作的算法：

Sorting all the arrays separately O(knlogn).
分别对所有阵列进行排序O（knlogn）。
Take two arrays A1 and A2 from the array of arrays.
从数组数组中取两个数组A1和A2。
Navigate through every item of A1 and search if the element is in A2 using binary search O(nlogn).
浏览A1的每个项目，并使用二分搜索O（nlogn）搜索元素是否在A2中。
Store the common elements from A1 and A2 into array B.
将A1和A2中的公共元素存储到数组B中。
Take another array from the arrays of arrays as A2, use array B as A1.
从阵列数组中取另一个数组作为A2，使用数组B作为A1。
Go to step 3 and repeat the process until you have used all the arrays in your array of arrays O(knlogn).
转到步骤3并重复该过程，直到您使用了阵列数组O（knlogn）中的所有数组。

Here's a pseudocode of the proposed algorithm (looks like Java code but is not Java code at all):

这是所提算法的伪代码（看起来像Java代码，但根本不是Java代码）：

public Comparable[] findCommonElements(Object[] collections) {
    //1.
    for each collection in collections
        Comparable[] compCollection = (Comparable[])collection
        sort(compCollection)
    end for
    //2.
    Comparable[] a1 = (Comparable[])collections[0]
    //assume MAX is a really high value like 10000
    //the best value for MAX would be the max length of the arrays in collections
    Comparable[] b = new Comparable[MAX]
    int bSize = 0
    //6.
    for i = 1 to collections.length - 1
        //5.
        Comparable[] a2 = (Comparable[])collections[i]
        //3.
        for each Comparable comp in a1
            int index = binarySearch(comp, a2)
            if index >= 0 then
                //4.
                add a2[index] into b
                bSize = bSize + 1
            end if
        end for
        //5.
        a1 = b
        b = new Comparable[MAX]
        bSize = 0
    end for
    return b
}

#1