如何使用 HashSet 查找两个 Comparable 数组中的共同元素？

Question

编辑：方法签名

    public Comparable[][] findCommonElements(Comparable[][] collections)

错了。应该是

    public Comparable[] findCommonElements(Comparable[][] collections)

但在我的 IDE 中更改它会使一切变得混乱。我几乎觉得我已经超出了我的知识范围，因为我不完全理解 Sets，而且 2D 数组把我搞得一团糟。

我需要编写一个算法，该算法采用两个 Comparable 数组，以 线性时间效率 遍历它们，并显示共同点元素。我读过使用 HashSet 会给我最快的时间效率，但我陷入了僵局。原因如下：

我们得到了说明和一行代码，即方法签名

public Comparable[][] findCommonElements(Comparable[][] collections)

这意味着我必须 return 二维数组，"collections." 我通过电子邮件向我的教授发送了有关使用 HashSets 的信息，我得到了批准，但我遇到了这个问题：

"You can use HashSets inside your findCommonElements method, but you will need to be able to count the number of comparisons performed. Although hashing is usually very efficient, some comparisons will be made in the event of collisions. To do this you would need to have access to the source code for the HashSet you use. You also need a "getComparisons()" 方法在你的 CommonElements class 到 return 比较的次数。"

两个学期的编程，HashSets、Maps、Tables等我都没有学，自己在努力学习，对碰撞也不是很了解。

我的代码确实采用了两个数组和 return 公共元素，但是我的 return 语句很奇怪，因为我基本上是这样写的，所以它可以编译（2d Comparable 数组是参数） .

我走的路对吗？这是代码：

public class CommonElements {

    static Comparable[] collection1 = {"A", "B", "C", "D", "E"}; //first array
    static Comparable[] collection2 = {"A", "B", "C", "D", "E", "F", "G"}; //second array
    static Comparable[][] collections = {collection1, collection2}; //array to store common elements. 
    static Set<Comparable> commonStuff = new HashSet<>(); //instance of Set containing common elements

    public static void main(String[] args) {

        CommonElements commonElements = new CommonElements(); //create instance of class CommonElements
        commonElements.findCommonElements(collections); //call the find method

    }
    public Comparable[][] findCommonElements(Comparable[][] collections) {

        Set<Comparable> addSet = new HashSet<>(); //instance of Set to add elements to

        for (Comparable x : collection1) { //adding elements from first array to my addSet
            addSet.add(x);
        }
        for (Comparable x : collection2) {
            if (addSet.contains(x)) {
            commonStuff.add(x); //checking for common elements, add to commonStuff Set
            }
        }
        System.out.println(toString(commonStuff)); //print the toString method

        return collections; //return statement, otherwise Java will whine at me
    }
    public String toString(Set<Comparable> commonStuff) { //this method gets rid of the brackets
        String elements = commonStuff.toString(); //make a String and assign it to the Set
        elements = elements.replaceAll("\[", "").replaceAll("\]", ""); //replace both brackets with empty space

        return "Common Elements: " + elements; //return the Set as a new String
    }
}

Answer 1

HashSet.add(E e) returns 如果无法将 e 添加到 Set，则为 false，因此我们可以说：

if (addSet.add(x)){
    //the collection did not contain x already
} else {
    //the collection contained x
}

所以你可以做的是这样的：

public Comparable[] findCommonElements(){
    Set<Comparable> collectionSet1 = new HashSet<>(Arrays.asList(collection1));
    Set<Comparable> collectionSet2 = new HashSet<>(Arrays.asList(collection2));
    for (Comparable x : collectionSet1){
        if (!collectionSet2.add(x)){
            commonStuff.add(x);
        }
    }
    return commonStuff.toArray(); //convert HashSet to an array
}

请注意，您需要 import java.util.Arrays;

Answer 2

编辑我忘了说我导入了 Apache Commons Array Utils。很有用。

我明白了。感谢你的帮助。我有一个调用 class 实例 3 次的主要方法和 3 个测试方法，但这些都是无关紧要的。这就是给我带来麻烦的原因，现在可以了。 :-)

public int getComparisons() {
        return comparisons;
    } //method to return number of comparisons
    public static Comparable[] findCommonElements(Comparable[][] collections) {
        /*
        I LEARNED THAT WE HAD TO USE MORE THAN TWO ARRAYS, SO IT WAS BACK
        TO THE DRAWING BOARD FOR ME. I FIGURED IT OUT, THOUGH.
        */
        Comparable[] arr1 = collections[0]; //set initial values to 1 Dimensional arrays so the test methods can read their respective values
        Comparable[] arr2 = collections[1];
        Comparable[] arr3 = collections[2];

        /*
        THE FOLLOWING BLOCK OF CODE TAKES ALL THE PERMUTATIONS OF THE 3 ARRAYS (i.e. 1,2,3; 1,3,2; 2,1,3, etc),
        DETERMINES WHICH ARRAY IS THE SHORTEST, AND ADDS THE LONGER TWO ARRAYS TO A QUERY ARRAY.
         */
        if(arr1.length < arr2.length && arr1.length < arr3.length || arr2.length <= arr3.length) { //shortest array will become hash array. the other two will become a combined query array.
            hashArray = arr1;  //these will be utilized below to put into Sets
            queryArray = ArrayUtils.addAll(arr2, arr3);
        }
        else if(arr2.length < arr1.length && arr2.length < arr3.length || arr1.length <= arr3.length) {
            hashArray = arr2;
            queryArray = ArrayUtils.addAll(arr1, arr3);
        }
        else if(arr3.length < arr1.length && arr3.length < arr2.length || arr1.length <= arr2.length) {
            hashArray = arr3;
            queryArray = ArrayUtils.addAll(arr1, arr2);
        }
        HashSet<Comparable> intersectionSet = new HashSet<>(); //initialize Sets
        HashSet<Comparable> arrayToHash = new HashSet<>();
        for(Comparable element : hashArray) { //add shorter array to hashedArray Set
            arrayToHash.add(element);
        }
        //NOTE FROM THE JAVADOC ON THE IMPLEMENTATION OF .contains() USING HASHSET COMPARISONS
        /**
         * <p>This class offers constant time performance for the basic operations
         * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
         * assuming the hash function disperses the elements properly among the
         * buckets.
         */
        for(Comparable element : queryArray) {
            if(element != null) {
                comparisons++; // increment comparisons with each search
            }
            if(arrayToHash.contains(element)) { //search for matches and add to intersectionSet (.contains uses the equals method to determine if an object is within array)
                intersectionSet.add(element);
            }
        }
        return intersectionSet.toArray(new Comparable[0]); //return Set as Array defined in method signature
    }

如何使用 HashSet 查找两个 Comparable 数组中的共同元素？

How to use HashSet to find common elements in two Comparable arrays?

java

arrays

hashset

comparable