java - 避免整数数组中的重复整数

Question

如何在不使用任何集合(即 Arraylist 或 Set 等)的情况下避免将重复整数添加到整数数组中？

Answer 1

解决方案取决于您的要求。如果您的数组大小(n<10^6)，则在每次插入时扫描数组就足够了，但如果您的数组很大且插入频繁，我会提出一个不同的解决方案。

在每次插入时扫描数组需要 O(n) 的复杂度。对于小数，开销可以忽略不计，但随着数组大小的增加，每次插入都遍历是低效的。

如果您需要性能并且内存不是您的限制，您可以采用 boolean 数组并将所有元素初始化为false。然后每当得到一个数字时，将其在 boolean 数组中的索引值设置为true，并在插入时检查是否为插入元素索引号处的 boolean 值。

这是初始化 boolean 数组的代码(初始化它会使所有元素都为假):

boolean [] duplicateValuesArray = new boolean[Integer.MAX_VALUE];

这是在数组中插入一个元素的函数:

    public void insertElement(int elementToBeInserted) {
        if(!duplicateValuesArray[elementToBeInserted])  //check if element already in array
            duplicateValuesArray[elementToBeInserted] = true;
            mainArray[index++] = elementToBeInserted;
    }

这样，每当你得到一个数字时， boolean 数组中该索引的值被设置为true，并且在插入时，每次检查索引，如果值为true ，该元素存在于数组中，请勿插入。

如果你有一个大的 ma​​inArray (n>10^6) 并且你有频繁的插入，那么这个的复杂性会低得多。这是因为，初始化一个 boolean 数组是一次O(n)复杂度，之后检查 boolean 数组中的元素和插入元素只是O(1) 操作，在恒定时间内发生。

因此，有效的复杂性降低到只初始化 boolean 数组。即使就内存占用而言，我也不介意，因为 boolean 原语只占用内存中的一位。

P.S:基本上这是内存与性能的权衡，这就是通用计算权衡，随处可见。