1

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

4

7 回答 7

2

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

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

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

这是初始化布尔数组的代码（初始化它会使所有元素都为假）：

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;
    }

这样，每当您获得一个数字时，布尔数组中该索引的值就会设置为true，并且在插入时，每次检查索引时，如果 value 为true，则该元素存在于数组中，不要插入它。

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

因此，有效的复杂性被降低到仅仅初始化布尔数组。即使在内存占用方面，我也不介意，因为布尔原语只占用内存中的一位。

PS：基本上这是内存与性能的权衡，这是无处不在的通用计算权衡。

于 2012-06-15T05:11:43.383 回答
1

如果您的问题是返回一个Integer[]，而不是任何其他集合，那么您可以使用Set<Integer> privately 来避免重复值，然后返回Set<Integer>.toArray(new Integer[0])。

恕我直言，这是最简单的方法...

例如：

private Set<Integer> intSet = new HashSet<Integer>();

public void setIntArray(Integer[] i){
    intSet = new HashSet<Integer>(Arrays.asList(i));
}

public Integer[] getIntArray(){
    return intSet.toArray(new Integer[0]);
}
于 2012-06-06T07:30:59.373 回答
1

您可以创建另一个布尔类型的数组，我们称之为它exists。然后每次将整数添加到主列表时，检查 if exists[newNumber]。如果值为真，则它已经存在，否则将数字添加到整数数组并将布尔值设置为真。

如果数字范围的界限很小，则此解决方案效果很好。请注意，我的示例还假设整数是正数。一些优化是使用 long[] 数组并将每个位用作标志。

于 2012-06-06T07:32:37.257 回答
1

我建议您首先执行Arrays.Sort(int[])。然后使用Arrays.binarySearch( int [] ,int )检查元素是否存在。

根据javadoc：

/**
 * Sorts the specified array of ints into ascending numerical order.
 * The sorting algorithm is a tuned quicksort, adapted from Jon
 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
 * 1993).  This algorithm offers n*log(n) performance on many data sets
 * that cause other quicksorts to degrade to quadratic performance.
 *
 * @param a the array to be sorted
 */
public static void sort(int[] a) {
sort1(a, 0, a.length);
}

对于 BinarySearch：

 /**
 * Searches the specified array of ints for the specified value using the
 * binary search algorithm.  The array must be sorted (as
 * by the {@link #sort(int[])} method) prior to making this call.  If it
 * is not sorted, the results are undefined.  If the array contains
 * multiple elements with the specified value, there is no guarantee which
 * one will be found.
 *
 * @param a the array to be searched
 * @param key the value to be searched for
 * @return index of the search key, if it is contained in the array;
 *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 *         <i>insertion point</i> is defined as the point at which the
 *         key would be inserted into the array: the index of the first
 *         element greater than the key, or <tt>a.length</tt> if all
 *         elements in the array are less than the specified key.  Note
 *         that this guarantees that the return value will be &gt;= 0 if
 *         and only if the key is found.
 */
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}

你知道元素是否存在，休息对你来说很容易。

于 2012-06-07T15:08:58.990 回答
0

不使用任何集合，即 Arraylist 或 Set 等？

只需在插入之前检查数组，

您可以使用插入排序并进行二进制搜索，它会快一点

于 2012-06-06T07:20:29.417 回答
0
  1. 编写一个将值添加到数组的方法。
  2. 添加之前，扫描数组是否存在值。
  3. 如果确实存在，请跳过添加。
  4. 仅使用该方法将值添加到数组中。
  5. 理想情况下，将数组和方法捆绑在一个类中。瞧：封装！
于 2012-06-06T07:20:43.130 回答
0

首先假设数组是一个缓冲区并且有额外的空间。

只需循环检查每个值。如

    for(int i=0;  i<endpointer  &&i < buffer.length  ; i++){
        if(buffer[i]==valueToPutInArray){
            valueExists=true;
            break;
        }
    }
    if(!valueExists)    {
        buffer[endpointer++]=valueToPutInArray;

    }

如果必须重新分配数组，那么您必须执行以下操作：

    int i=0;
    Integer[] outputArray = new Integer[buffer.length+1];
    for(Integer value : buffer) {
        if(value==valueToPutInArray){
            valueExists=true;
            break;
        }
        outputArray[i++]=value;
    }
    if(!valueExists)    {
        outputArray[i]=valueToPutInArray;

    }
于 2012-06-06T18:49:36.037 回答