整數長時間的HashMap

-2

我有一個從0到數組長度的數組，除了一些數字丟失，我必須找到它。整數長時間的HashMap

public static Integer findNumber(Integer[] array){ 
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for(Integer number : array){ 
     map.put(number, 1); 
    } 
    for(Integer i=0; i<array.length; i++){ 
     if(map.get(i)==null) 
      return i; 
    } 
    return -1; 
}

我認爲這是要成爲一個很好的解決方案，但將需要很長的時間，整理與統計重複的解決方案是快了很多，我不知道爲什麼。整數散列是Integer本身，所以在計算散列時甚至沒有時間浪費，也沒有用等號進行迭代（這取決於數字，我選擇了只有一個副本的例子）。我覺得我在這裏錯過了一些明顯的東西。我試着指定初始容量和負載因數，但這隻會讓事情變得更糟。我能以某種方式優化它嗎？

這需要花費大量的時間，而不是迭代尋找解決方案，就像95％的執行時間。

來源

2016-07-11 Haratino

由於很多拳擊/拆箱發生，速度會變慢嗎？ – kaqqao

一套比地圖稍快。 –

我也這麼認爲，我從原始整數開始，然後改爲整數，根本沒有任何改變。我認爲即使它讓事情變得更慢，它也不會讓它們變得更慢。 – Haratino

-1

我想有一個更簡單的解決方案。試試這個：

public static Integer findNumber(Integer[] array){ 

    for(Integer i=0; i<array.length; i++){ 
     if(i != array[i]) 
      return i; 
    } 
    return -1; 
}

希望能幫到你。

來源

2016-07-11 09:20:25 mrk

我不認爲這會工作，例如：'array = {2,1,3}'缺少的數字應該是0，但您的代碼將返回2 – niceman

此代碼既不處理重複數字或未排序的數組。 – Tom

對不起，我不太瞭解這個問題。但經過一些研究，我認爲他在找什麼（數學）在這裏回答[http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers ]（http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers） – mrk

而不是Map，可以使用（原始）布爾數組。在第一循環中，而不是把1你翻轉陣列的細胞爲真： boolArray[number] = true;

後，環陣列上，並找到失蹤數

來源

2016-07-11 09:21:37

是的，這實際上是我想用地圖實現的想法，我認爲map會和這個一樣快，也許只是慢一點，因爲它在底層做了幾乎相同的事情，比方說，我把20號放在地圖上，它計算的散列是相同的，然後它internalArray [20] = 1，就像boolArray [number] = true。 – Haratino

不同的是，你填寫你它，而不是數量陣列上迭代布爾數組後，看到我的其他答案 - 迭代在地圖上的值來搜索空 –

，如果你堅持使用地圖：第二循環應不走在陣列上，而是在地圖的價值，尋找空一個：

map.values().stream().filter(v -> v == null).findFirst();

來源

2016-07-11 09:30:57

你可以去簡單，更快捷的方式：在陣列和整數，然後從減去它（這是數的總和從1到n）。剩餘價值是缺少的數字。

來源

2016-07-11 09:38:21 kkonrad

像很多這些謎題這是一個數學技巧，他們是尋找，而不是編程。 +1 –

整數長時間的HashMap

回答

相關問題