logo标签列表

在Java中维护一个唯一数组的ArrayList

javaarraylist
17

如何维护一个包含唯一数组的 ArrayList？

例如，如果我有以下数组：

int [] a = {1,2,3};
int [] b = {2,1,3};
int [] c = {2,1,3};

根据我的逻辑，我正在考虑独特的组合。因此，在上面的情况下，a = b = c，因为它们都包含"1"、"2"和"3"。

理想情况下，我想知道Java中是否有一种数据结构可以识别这个问题。

我尝试了以下方法：

Set<int []> result = new LinkedHashSet<>();
int [] x = {1,2,3};
int [] z = {2,1,3};
int [] m = {2,1,3};

result.add(x);
result.add(z);
result.add(m);

for(int [] arr: result){
    printArray(arr);
}

我的输出结果是：

1 2 3
2 1 3
2 1 3

理想情况下，我希望我的输出只打印上述组合中的一个。

8
如果元素顺序不重要且不允许重复，则使用 Set<Integer> 而不是 int[] 将提供您想要的相等关系。 - John Bollinger
1
你的数组大小固定为3吗？如果是，你可以实现一个类来计算这3个元素的哈希码。 - SomeDude
2
@computercarguy：你完全错了。主集合将使用其集合元素的哈希码实现。对于大多数良好实现的集合，哈希码()会在其元素上递归调用。只有对于数组和默认（未重写）哈希码实现才使用地址。 - Ricola
1
@JohnBollinger 我认为 Set<Integer> 中元素的 hashCode 只是单个代码的相加，我从 AbstractSet 类中的实现可以看出来：public int hashCode() {int h = 0;Iterator<E> i = iterator();while (i.hasNext()) {E obj = i.next();if (obj != null)h += obj.hashCode();}return h;} 在这种情况下，Set<Set<Integer>> 不会起到作用，它会认为 {0,1,2} 和 {1,1,1} 相等。 - SomeDude
2
问题的标题明确提到了ArrayList，尽管问题实际上是关于Set的。是否有任何反对将标题更改为类似于“维护一个集合...”或“维护一个collection...”的内容？ - Marco13
显示剩余10条评论
7个回答
5
您可以创建一个方法来实现“如果不等于则添加”的功能，如下所示：
public static Set<int[]> addIfNotExist(Set<int[]> result, int[] array) {
    Arrays.sort(array);
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                return Arrays.equals(a, array);
            });
    if (check) {
        return result;
    } else {
        result.add(array);
        return result;
    }
}

然后你可以这样调用你的方法：
result = addIfNotExist(result, x);
result = addIfNotExist(result, z);
result = addIfNotExist(result, m);

输出

[1, 2, 3]

或者如果您使用静态的Set，可以直接使用:
static Set<int[]> result = new LinkedHashSet<>();

public static void main(String[] args) {

    int[] x = {1, 2, 3};
    int[] z = {2, 1, 3};
    int[] m = {2, 1, 3};

    addIfNotExist(result, x);
    addIfNotExist(result, z);
    addIfNotExist(result, m);

    for (int[] arr : result) {
        System.out.println(Arrays.toString(arr));
    }
}

public static void addIfNotExist(Set<int[]> result, int[] array) {
    Arrays.sort(array);
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                return Arrays.equals(a, array);
            });
    if (!check) {
        result.add(array);
    }
}
我有一个Java问题，也许你能帮我解决 https://stackoverflow.com/questions/57792705/java-cannot-find-symbol-symbol-class-item - Dinero
@Dinero 抱歉，您的问题已被删除，您能否恢复它？然后您将会得到答案 ;) - Youcef LAIDANI
@YCF_L 调用 Arrays.sort 对于每个数组来说不是太昂贵了吗？据我所知，这个方法是原地排序的，因此通过调用 addIfNotExist，我们实际上保存了一个已排序的数组，因此我们不必在另一个调用中再次对所有存储的数组进行排序。如果我错了，请纠正我；> - Andronicus
谢谢@Andronicus，你说得完全正确，我会进行编辑的 :-) - Youcef LAIDANI
@YCF_L，不！是你在SO上发布了所有这些精彩答案，感谢你！ - Andronicus
不客气，@Andronicus，也谢谢你，你也提供了很多好的答案。 - Youcef LAIDANI
5

这种做法可能感觉有些不专业，但你可以使用一个带有自定义Comparator的TreeSet。根据您的需求，它可能确实可行，但请注意，这是违反了Set接口的常规契约。

class Demo {
    public static void main(String[] args) throws Exception {
        Set<int[]> result = new TreeSet<>(new Hack());
        int[] x = {1,2,3};
        int[] z = {2,1,3};
        int[] m = {2,1,3};

        result.add(x);
        result.add(z);
        result.add(m);

        for (int[] arr : result) {
            System.out.println(Arrays.toString(arr));
        }
    }
}

class Hack implements Comparator<int[]> {

    @Override
    public int compare(int[] e1, int[] e2) {
        int[] copy1 = Arrays.copyOf(e1, e1.length);
        int[] copy2 = Arrays.copyOf(e2, e2.length);
        Arrays.sort(copy1);
        Arrays.sort(copy2);
        return Arrays.compare(copy1, copy2);
    }
}

输出：

[1, 2, 3]

如果你仍在使用Java 8，请使用这个“Hack”实现：
class Hack implements Comparator<int[]> {

    @Override
    public int compare(int[] e1, int[] e2) {
        int[] copy1 = Arrays.copyOf(e1, e1.length);
        int[] copy2 = Arrays.copyOf(e2, e2.length);
        Arrays.sort(copy1);
        Arrays.sort(copy2);
        int cmp = Integer.compare(copy1.length, copy2.length);
        if (cmp != 0) {
            return cmp;
        }
        for (int i = 0; i < copy1.length; i++) {
            cmp = Integer.compare(copy1[i], copy2[i]);
            if (cmp != 0) {
                return cmp;
            }
        }
        return 0;
    }
}
1
这似乎会很慢，最好的情况下会因为树退化而变得缓慢，最糟糕的情况是错误的--如果 compare 不是对称关系，那么树要么会变成退化的树，要么将无法正常工作。 - nanofarad
1
@Ricola 好的，我收回关于树变得退化的评论（我确实看到Javadoc保证了具有某种平衡树的对数时间操作）。 但是，这在使用示例时会出现故障：https://gist.github.com/hexafraction/607329bdc33c27a9f3b6044beec48137（请注意最终输出的第一行和最后一行）。这绝对需要进行真正的、对称的比较。 - nanofarad
@AndreyAkhmetov：compare的实现有点太草率了。感谢你提供的要点！ - Marvin
1
使用Java 9+，您可以简单地使用Arrays.compare()。 - Ricola
1
@Ricola：好观点！我会修改的，现在Java 9+应该是标准了。 - Marvin
显示剩余4条评论
2
假设我们假定您的数组不能包含多个相同的整数（例如 [1, 1, 2]），那么您对数组唯一性的定义（具有相同的元素而不考虑顺序）与 Set 的定义相同，因此您可以使用 Set of Set。"Original Answer"可以翻译成"最初的回答"。
public static void main(String[] args){
    Set<Set<Integer>> result = new HashSet<>();
    int [] x = {1,2,3};
    int [] z = {2,1,3};
    int [] m = {2,1,3};

    result.add(arrayToSet(x));
    result.add(arrayToSet(z));
    result.add(arrayToSet(m));

    System.out.println(result);

}

private static Set<Integer> arrayToSet(int [] arr){
    return Arrays.stream(arr).boxed().collect(Collectors.toSet());
}

如果你想保留你的数组，那么当两个数组具有相同元素时，应该保留哪一个？如果是先添加的第一个数组，你可以使用一个 Map<Set<Integer>, int[]>，然后你的 map 的值包含这些数组。
如果需要考虑到它可能包含多次相同的整数，那么这些就是Multisets。你可以通过一个 Map<Integer, Integer> 实现 Multiset，它计算每个元素出现的次数。然后你可以使用相同的实现，但是用 Set<Map<Integer, Integer>> 代替 Set<Integer>：
public static void main(String[] args){
    Set<Map<Integer,Long>> result = new HashSet<>();
    int [] x = {1,2,3};
    int [] z = {1,2,2,3};
    int [] m = {1,2,3,2};

    result.add(arrayToMultiSet(x));
    result.add(arrayToMultiSet(z));
    result.add(arrayToMultiSet(m));

    System.out.println(result);

}

private static Map<Integer,Long> arrayToMultiSet(int [] arr){
    return Arrays.stream(arr).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}

注意：我使用了Map<Integer,Long>，因为Collectors.counting（）返回一个Long类型的收集器。

最初的回答
2

已经有一些回答了，但其中一些做出了某些无法从问题中推导出的假设，另一些建议某些可能被视为解决方法的更改，还有一些具有某些不应被忽视的缺点。

在此澄清其中一些：

最初的回答：

  • Changing the elements to a Set<Integer> makes the assumption that each element may only appear once. Additionally, if the existing code already creates the int[] arrays, and the downstream code needs the int[] arrays, then using the resulting data structure would be clumsy:

    int array[] = somewhere.getArray();
Set<Integer> set = convert(array); // Convert array to set
data.add(set);
...
set = data.iterator().next();
array = convert(set);              // Convert set to array
somewhere.setArray(array);

    Depending on the size of the arrays, this may have an impact on performance and generate some memory overhad.

  • Using a TreeSet<int[]> looks like a simple and reasonable solution. The nicest thing is that it can directly store the int[] arrays. But it has some drawbacks:

    1. It implies an ordering. It is no longer possible to use another Set implementation (like a LinkedHashSet) that retains the insertion order
    2. It may be a bit tricky to implement the comparison in a way that is consistent with equals, and failing to do so will cause the set to no longer obey the general contract of the Set interface
    3. A simple but correct implementation of the comparison will likely involve sorting the arrays. This means that the arrays might either have to be modified by their insertion into the set, which is certainly not acceptable, or one would have to create defensive copies of the arrays. Here, one has to keep in mind that the copy and the sorting will have to be done each and every time when a new array is added, and it will have to be done multiple times while going down the tree. Although the number of comparisons will only be O(log(n)) for a set with n elements, sorting will take O(m log(m)) each time for arrays of length m, which may be prohibitively expensive.
  • Similar arguments may be applied for the approaches that check whether an "equivalent" array already exists before inserting a new one. Additionally, these approaches are not based on a data structure, but have to be part of the code that uses the data structure.
出于这些原因，我会选择与Mykhailo Moskura在他的回答中提到的方法基本相同：它基于一个简单地包装给定的int[]数组，并相应地实现equals和hashCode。
（请注意，您也可以让该类实现Comparable，增加一些灵活性，以确定是否可以将其放入TreeSet中，如果您了解上述可能存在的困难和缺点...）
在下面的示例中，此类称为UnorderedIntArray。 从概念上讲，最好拥有一个Set<int[]>，而下面的解决方案必须使用Set<UnorderedIntArray>。但由于此类仅包装现有数组，因此性能和内存开销几乎为零，因此我仍然认为它比在int[]和其他某种数据类型之间进行转换更具优势。还请注意，下面示例中的equals方法不是非常高效，但它是确保遵守equals合同的简单方法。
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class UniqueArraysTest {

    public static void main(String[] args) {
        Set<UnorderedIntArray> result = new LinkedHashSet<>();
        int[] x = { 1, 2, 3 };
        int[] y = { 2, 1, 3 };
        int[] z = { 2, 1, 3 };

        int[] u = { 1, 1, 1, 2, 3 };
        int[] v = { 1, 1, 1, 2, 3 };
        int[] w = { 1, 1, 1, 1, 3 };

        result.add(new UnorderedIntArray(x));
        result.add(new UnorderedIntArray(y));
        result.add(new UnorderedIntArray(z));
        result.add(new UnorderedIntArray(u));
        result.add(new UnorderedIntArray(v));
        result.add(new UnorderedIntArray(w));

        for (UnorderedIntArray a : result) {
            int[] array = a.getArray();
            System.out.println(Arrays.toString(array));
        }

    }

    static class UnorderedIntArray {
        private final int array[];

        UnorderedIntArray(int array[]) {
            this.array = array;
        }

        int[] getArray() {
            return array;
        }

        @Override
        public int hashCode() {
            return IntStream.of(array).sum();
        }

        @Override
        public boolean equals(Object object) {
            if (object == this) {
                return true;
            }
            if (object == null) {
                return false;
            }
            if (!(object instanceof UnorderedIntArray)) {
                return false;
            }
            UnorderedIntArray that = (UnorderedIntArray)object;
            if (this.array.length != that.array.length) {
                return false;
            }
            // This is very simple, but not very efficient. More efficient
            // solutions could be implemented, but they are not trivial...
            Map<Integer, Long> thisFrequencies = computeFrequencies(this.array);
            Map<Integer, Long> thatFrequencies = computeFrequencies(that.array);
            return thisFrequencies.equals(thatFrequencies);
        }

        private Map<Integer, Long> computeFrequencies(int array[]) {
            return Arrays.stream(array).boxed().collect(
                Collectors.groupingBy(Function.identity(), Collectors.counting()));
        }

        @Override
        public String toString() {
            return Arrays.toString(array);
        }

    }
}

最初的回答

对于输入的内容

int[] x = { 1, 2, 3 };
int[] y = { 2, 1, 3 };
int[] z = { 2, 1, 3 };
int[] u = { 1, 1, 1, 2, 3 };
int[] v = { 1, 1, 1, 2, 3 };
int[] w = { 1, 1, 1, 1, 3 };

最初的回答是输出符合预期。
[1, 2, 3]
[1, 1, 1, 2, 3]
[1, 1, 1, 1, 3]
1
你可以创建一个包装类，其中包含一个不可变的整数数组实例变量，并重写哈希码：
public class ArrayWrapper {
   private final int[] a;

@Override
public int hashCode(){
 //your implementation 
}
@Override
 public boolean equals(){
  // your implementation 
 }
}

然后您可以使用：

Set<ArrayWrapper> set = new HashSet<>();
1
在覆盖hashCode而不是equals时几乎总是会出错 - 即使hashcode编写得很好，也不能保证在冲突的情况下工作，即使在这种情况下，您也没有实际指定如何编写适当的hashCode来解决此问题。 - nanofarad
我认为这是一个合理的方法（与此处提出的一些替代方案相比），并且我在我的答案中采用了它。不过，这个答案有点太简短和粗略了，不能得到+1的评价（抱歉...） - Marco13
1
你似乎需要一组整数集合，如果相对顺序对你很重要，可以使用类似以下这样的方法：
import java.util.Set;
import java.util.LinkedHashSet;
import java.util.Arrays;
import java.util.stream.Collectors;

public class HelloWorld
{
  public static void main(String[] args)
  {
        Set<Set<Integer>> result = new LinkedHashSet<>();
        int[] x = {1, 2, 3};
        int[] z = {2, 1, 3};
        int[] m = {2, 1, 3};

        result.add(Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(z).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(m).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));

        System.out.println(result);
  }
}

你可以将Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new))提取到单独的函数中。
1
@Test
    public void testArraysSet() {
        Set<int[]> myArrays = new TreeSet<>((arr1, arr2) -> {
            Arrays.sort(arr1);
            Arrays.sort(arr2);
            return Arrays.equals(arr1, arr2) ? 0 : 1;
        });

        int [] a = {1,2,3};
        int [] b = {2,1,3};
        int [] c = {2,1,3};

        myArrays.add(a);
        myArrays.add(b);
        myArrays.add(c);

        assertEquals(1, myArrays.size());
    }

这样做应该可以，但排序可能会稍微减慢速度。您可能需要研究更快的数组比较方法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接