在Java中找到整數只出現在未排序整數數組中

我給出了一個未排序的整數數組，其中每個整數只出現兩次，排除只出現一次的整數。我想用Java編寫一個程序來查找只出現一次的整數。在Java中找到整數只出現在未排序整數數組中

這裏是我的嘗試：

int findIntegerThatOccursOnce(int[] arr) 
{ 
    HashSet<Integer> hashSet = new HashSet<Integer>(); 
    int mSum = 0; 
    for(int i = 0; i < arr.length; i++) 
    { 
     if(hashSet.contains(arr[i])) 
     { 
      mSum = mSum - arr[i]; 
     } 
     else 
     { 
      hashSet.add(arr[i]); 
      mSum = mSum + arr[i]; 
     } 
    } 
    return mSum; 
}

我的教授說，這是一個很好的嘗試，但存在使用更少的空間一個更好的，但我不能看我怎麼可以用更少的空間做呢？任何人都可以幫忙解釋一下空間問題嗎？

來源

2017-06-01 Aarron Smith

我投票結束這個問題作爲題外話，因爲這是工作代碼，並要求代碼審查。所以它屬於https://codereview.stackexchange.com –

在嘗試提出更多問題之前，請閱讀[我應避免詢問什麼類型的問題？]（http://stackoverflow.com/help/dont-ask）。 –

@JarrodRoberson我想知道爲什麼我的解決方案對空間不利，我更新了我的問題 –

你嘗試採取爲O（n）時間和爲O（n）空間，真的是相當不錯的，因爲有很多簡單平凡的解決方案，在時間和空間「雪上加霜」的。

如果您對陣列中的所有整數使用Exclusive or (XOR)，則可能需要更少空間的一種可能的解決方案是：因爲所有發生兩次的整數都會被取消。

這會給你一個只出現一次的整數。此解決方案將使用O（1）空間。

來源

2017-06-01 02:28:14 shash678

假設斷言所有數字出現兩次，除了一個值您可以異或所有的值並返回結果。像，

static int findIntegerThatOccursOnce(int[] arr) { 
    int v = 0; 
    for (int i : arr) { 
     v ^= i; 
    } 
    return v; 
}

來源

2017-06-01 02:29:03

在Java中找到整數只出現在未排序整數數組中

回答

相關問題