Java 查找集合中的公共(public)元素

Question

我需要使用以下方法在数组集合中找到公共(public)元素

public Comparable[] findCommonElements(Object[] collection)

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

我想对数组进行快速排序 (??)，然后对公共(public)元素进行二进制搜索。这应该使我的 O(knlogn) 正确，但我不能 100% 确定效率。

我不知道如何使用二进制搜索来搜索集合，然后打印公共(public)元素。我知道我不能从静态方法调用 common ，但我把它留给了我尝试过的想法。我知道我的时间最好花在学习如何使用数组列表和哈希集上，但我应该使用已经涵盖的概念，而这些概念还没有。

代码:

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

感谢您的帮助和意见!

Answer 1

根据我的评论，这里有一个算法可以完成您的工作:

1. 分别对所有数组进行排序 O(knlogn)。
2. 从数组的数组中取出两个数组A1和A2。
3. 遍历 A1 的每一项，并使用二进制搜索 O(nlogn) 搜索该元素是否在 A2 中。
4. 将A1和A2的公共(public)元素存入数组B。
5. 从数组的数组中取另一个数组作为A2，用数组B作为A1。
6. 转到第 3 步并重复该过程，直到您用完数组 O(knlogn) 中的所有数组。

这是建议算法的伪代码(看起来像 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
}