將原始int數組轉換爲列表

我正在嘗試解決以下問題。有兩個大小爲n的數組A和大小爲n + 1的B數組。 A和B具有相同的所有元素。 B有一個額外的元素。找到元素。將原始int數組轉換爲列表

我的邏輯是數組列表並檢查B中的每個元素存在於A.

但是，當我使用的基本數組我的邏輯是行不通的轉換。如果我正在使用

Integer [] a ={1,4,2,3,6,5}; 
Integer [] b = {2,4,1,3,5,6,7};

我的代碼工作正常。

public static void main(String [] args) 
{ 
    int [] a ={1,4,2,3,6,5}; 
    int [] b = {2,4,1,3,5,6,7};  
    List<Integer> l1 = new ArrayList(Arrays.asList(a)); 
    List<Integer> l2 = new ArrayList(Arrays.asList(b)); 
    for(Integer i :l2) 
    { 
     if(!l1.contains(i)) 
     { 
      System.out.println(i); 
     }   
    } 
}

而且我的邏輯是O（n + 1）。有沒有更好的算法。

感謝

來源

2011-09-23 javaMan

你的邏輯是N * M個，基本上平方（N^2），因爲數組中的每個元素你第二陣列中做搜索，在詞典/地圖搜索的情況下，它會更快，但你的情況與列表是一個^ 2 – sll

它不是原始陣列工作的原因，就是Arrays.asList給出當INT []返回List < Integer []>而不是List < Integer>。

番石榴在Ints類有這個答案。是有一個asList方法，將採取一個INT []並返回列表<整數>

更新

int[] a = ...; 
int[] b = ...; 
List<Integer> aList = Ints.asList(a); 
List<Integer> bList = Ints.asList(b);

以上將讓你的代碼爲INT正常工作[]因爲它適用於Integer []。

退房Ints API

來源

2011-09-23 14:41:26

我將代碼修改爲List l1 = new ArrayList（Arrays.asList（a））; \t List l2 = new ArrayList（Arrays.asList（b））; \t爲（整數[] i的：L2）（！l1.contains（I [0] .intValue（））） \t { \t如果 \t { \t的System.out.println（ⅰ）; \t} \t} – javaMan

即使是現在它不工作。你能更詳細地更新 – javaMan

嗎？注意我正在使用Ints.asList NOT Arrays.asList。這是一個番石榴庫功能，所以你需要包括番石榴罐。 –

你可以從你的兩個數組構造兩個Set<Integer>對象，然後用removeAll()找到額外的元素。

P.S.你似乎認爲你的方法不是O(n)。對於整體方法是O(n)，循環的每次迭代必須在恆定時間內執行;我把它作爲練習讓讀者弄清楚是否是這種情況。

來源

2011-09-23 14:38:30 NPE

那麼O是什麼？我在想O（n^2）（n-squared） –

@aix我認爲我的算法是O（n）。因爲我一次循環遍歷B的所有元素。等到它結束的時候，我們就完成了。我錯了嗎？ – javaMan

@aix我試圖實現你的邏輯。 – javaMan

計算每個數組的總和。 SUM（B） - 合計（）會給你額外的元素B.

來源

2011-09-23 14:40:37 rossum

不錯。這假定只有一個元素是不同的。但是，如果這是它工作得很好，是真正澳情況下（N） –

爲整型和長，並不一定是布爾值，雙打，漂浮 –

@MatthewFarwell布爾將工作太，無論是在「+是XOR」解釋和「 true is 1「interpretation – harold

將包含一個ArrayList的方法其實並不那麼有效。這個allone的運行時間爲O（n），所以你的算法的運行時間爲O（n^2）。

我建議將一個數組放在HashSet中（使用contains（）運行時O（1））。您可以保持原樣並直接遍歷數組。那麼你的運行時間是O（n）。

更新： 從HashSet API doc：

這個類提供了基本操作（添加，刪除，包含和大小）固定的時間性能，假定哈希函數將分散的元素正確的桶中。

我認爲默認的整數散列函數滿足要求。

來源

2011-09-23 14:43:31 vanje

它真的是O（n）嗎？由於HashMaps conatins方法不完全是O（n）。 O-ness取決於元素的數量與桶的數量。 –

@John B：我相信因爲array有不同的值，所以不會創建桶。 – sll

@venje不一定是對的。根據equals/hashCode合約，不同的值可能具有相同的hashCode。雖然這可能是一個安全的假設，即每個int值都有一個唯一的hashCode（因爲hashCode）返回int，但這不會是長期的事情，我認爲這不是一個安全的假設。這就是說，我不知道O因素真的是這裏的問題。 :) –

構造單個Set<Integer>對象。由於一個Set不能有重複的元素，添加所有的A，那麼你可以使用Add函數找到一個在B中返回true的條目。很好很容易。

來源

2011-09-23 14:44:20 BenCole

只是爲了興趣，因爲這將是因爲陣列串聯操作有點複雜，但另一個業務將採取O(n)

將兩個陣列一個陣列
XOR項目
都是一樣的項目將自動刪除，單個元素將是最後一個。

來源

2011-09-23 14:46:50 sll

不妨將它們留在單獨的數組中並循環兩次.. – harold

最快的方法是使用int[]，使用Arrays.sort併合並結果。我懷疑它是功課，所以我會把實際的解決方案留給自己。這是O（n * log（n）），但該常量低於使用包裝對象和集合。

如果您知道值範圍有限，則可以使用BitSet。這將檢測到多個差異，並且仍然是O（n）

如果您知道只有一個差異，請將比較結果作爲@rossum的建議。

來源

2011-09-23 14:48:13

只適用於那些有興趣的，對rossum的邏輯典型的解決方案。但是，如果我們有大數字，那麼可能會出現一些溢出問題。

這個alg很簡單，我們從w的零值開始，從一次數組中減去另一個數組中的元素，最後我們添加n + 1元素。

這將爲O工作（N）（在n爲n + 1）

我假定陣列b具有多個元件。

long result = 0; 

for(int i =0; i < a.length; i++) { 
    result -= a[i]; 
    result += b[i]; 
} 

result += b[a.length];

而在結果我們有我們的不同。

編輯：

哈羅德，在這裏我們不需要擔心內存提出更好的解決方案。

int result = 0; 

for(int i =0; i < a.length; i++) { 
    result ^= a[i]^b[i]; 
} 

result ^= b[a.length];

來源

2011-09-23 15:09:31

溢出並不重要，結果仍然正確 - 或者您可以使用XOR並且沒有溢出 – harold

將原始int數組轉換爲列表

回答

相關問題