在整數數組中避免重複的整數

Question

如何在不使用任何集合（即Arraylist或Set等）的情況下避免將重複的整數添加到整數數組中？

Answer 1

如果你的問題是返回一個Integer[]，而不是任何其他集合，你可以使用，無論一個Set<Integer>private LY避免重複值，然後返回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]); 
} 

Answer 2

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

只是通過陣列插入前檢查，

你可以使用insertion sort並做binarysearch它會更快一點

Answer 3

1. 寫，增加值到陣列的方法。
2. 添加前，如果值存在，請掃描數組。
3. 跳過添加如果它存在。
4. 僅限使用將值添加到數組的方法。
5. 理想地將數組和方法捆綁在一個類中。 Voila：封裝！

Answer 4

您可以創建另一個數組，我們稱之爲exists，boolean類型。然後每次向主列表添加一個整數時，檢查是否爲exists[newNumber]。如果該值爲true，則它已經存在，否則將該數字添加到整數數組並將布爾值設置爲true。

如果數字範圍有一個小的界限，此解決方案運作良好。請注意，我的示例還假定整數是正數。一些優化是使用long []數組並將每個位用作標誌。

Answer 5

首先假設數組是一個緩衝區並有額外的空間。

簡單地遍歷它檢查每個值。如

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; 

    } 

Answer 6

我建議你首先執行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); 
} 

和二分查找：

/** 
* 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); 
} 

而且一個你知道的元素中是否存在與否，剩下的就是容易讓你。

Answer 7

解決方案取決於您的要求。如果你有一個小陣列大小（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，並且在插入時，每次檢查索引時，如果值爲true，那個元素存在於數組中，不要插入它。

的這種複雜性要低得多，如果你有一個大的mainArray（N> 10^6），你有頻繁的插入。這是因爲初始化一個布爾數組是一次複雜度，之後檢查布爾數組中的元素和插入元素的操作只是在不變的時間內進行。

因此，有效的複雜性被簡化爲初始化布爾數組。即使在內存佔用方面，我也不介意，因爲布爾原語只佔用內存中的一位。

P.S：基本上它是一種內存vs性能的折衷，這是隨處可見的Universal Computing Trade off。