從數組中查找缺少的數字

編寫此代碼，想要使用任何算法找到更好的方法從已排序或未排序的數組中找到缺失的數字。如果它是一個未排序的數組，我將排序並執行以下操作。從數組中查找缺少的數字

private static void identifyMissingValues(Integer[] ar) { 

     for(int i = 0; i < (ar.length - 1); i++) { 

      int next = ar[i + 1]; 
      int current = ar[i]; 
      if((next - current) > 1) { 
       System.out.println("Missing Value : " + (current + 1)); 
      } 
     } 
    }

任何代碼更快或更好，請建議。

來源

2016-04-15 srikanth

如果只有一個數字從序列丟失，你可以總結一下所有你有量擬合選取，總結整個期望的序列，然後從另一個減去一個總和，以獲得失蹤號碼 – SimY4

如果有兩個或更多的連續錯過，只有第一個將被打印 – Rustam

我可以知道輸入和期望輸出數列嗎？
根據你的代碼，我覺得該系列應該是1的差異，如果我沒有錯。

來源

2016-04-15 10:24:02 Pavan

這不是答案。它應該像評論一樣發佈。 –

@EdgarRokyan我沒有足夠的積分發表評論。 – Pavan

因此，你有一個n元素的數組，它以一個整數i開始，幷包含從i到i + n的所有整數，是嗎？例如：

arr = [1,2,3,4,5]

因此，所有的數字數組中的總和應數的總和從i到I + N。

如：sum(arr) = 1+2+3+4+5 = 15

爲數字1到n的總和計算公式爲n(n+1)/2

所以，你可以有一個for循環：

int counter = 0; 

for(Integer i : integers) 
    counter += i

要獲取數字的總和你的數組。

如果您的陣列從一開始，您檢查counter變量是否等於n(n+1)/2，其中n是您的數組的長度。

如果你的陣列不是從一個開始的，例如arr = [78, 79, 80, 81]那麼你需要稍微調整一下這個方法，但我相信你可以確定它。

來源

2016-04-15 10:25:51 MrD

該算法如何告訴你哪些數字丟失？（除非只有一個數字缺失，這似乎並不是基於問題中的代碼）。 – Eran

排序數組需要O(n*log(n))。

你可以做的更好，如果你在陣列中的所有元素添加到HashSet(O(n))運行時間，然後0和ar.length - 1（或任何相關的範圍）的HashSet是否包含數之間檢查每個號碼。這將需要O(n)時間。

來源

2016-04-15 10:26:18 Eran

但你爲什麼要分類呢？ – MrD

@MrD我不想對它排序 - 有OP（如果它是一個未排序的數組，我將排序並執行以下操作）。這就是爲什麼我提供了一個不需要排序的選擇。 – Eran

@Eran使用HashSet對於較大的數據集，I.e時間複雜度（O（n））總是更好地執行。對？ – srikanth

你可以這樣做：

Set<Integer> mySet = new TreeSet<Integer>(Arrays.asList(ar)); 
int min = mySet.first(); 

for (int i = 0; i < mySet.size(); i++) { 
    int number = min + i; 
    if (!mySet.contains(number)) { 
     System.out.println ("Missing: " + number); 
     i--; 
    } 
}

來源

2016-04-15 10:32:35 dquijada

任何代碼比這更快，更好，請建議。

沒有有沒有這樣的事 - 你不能在一個O(n)算法改善，如果每一個元素都必須被訪問。

來源

2016-04-15 10:37:27 OldCurmudgeon

我們可以用O（n）算法以外的任何其他方式重寫代碼以查找多個缺失值嗎？ – srikanth

@srikanth - 是的 - 但效率不高。 – OldCurmudgeon

您的方法很好，但我添加了一些更多的數字，因爲缺少多個數字..

eg : ar={1,2,4,6,10} // Sorted Array 

private static void identifyMissingValues(Integer[] ar) { 
    for (int i = 0; i < (ar.length - 1); i++) { 
     int next = ar[i + 1]; 
     int current = ar[i]; 
     if ((next - current) > 1) { 
      for (int ind = 1; ind < next - current; ind++) 
       System.out.println("Missing Value : " + (current + ind)); 
     } 
    } 
}

輸出是，

Missing Value : 3 
Missing Value : 5 
Missing Value : 7 
Missing Value : 8 
Missing Value : 9

來源

2016-04-15 10:47:36

輸出必須是'3 5 7 8 9'。 – saka1029

是的你是正確的，但代碼是正確的。 –

Integer [] list = new Integer[]{1, 12, 85, 6, 10}; 


Integer previous = null; 


Arrays.sort(list); 

System.out.println(list); 


for(int index = 0; index < list.length; index++){ 


    if(previous == null){ 
     previous = (Integer) list[index]; 
     continue; 
    } 

    Integer next = previous + 1; 
    if(((Integer) list[index] - previous) > 1){ 

     System.out.println("Missing value " + next); 
     index--; 

    } 
    previous = next; 


}

來源

2016-04-15 11:07:16

使用位集合，而不是分選。

int[] ar = {7, 2, 6, 8, 10, 4, 3, 2}; 
    int min = IntStream.of(ar).min().getAsInt(); 
    BitSet b = new BitSet(); 
    for (int i : ar) 
     b.set(i - min); 
    int i = 0; 
    while ((i = b.nextClearBit(i + 1)) < b.length()) 
     System.out.println(i + min);

結果

5 
9

來源

2016-04-15 11:29:16 saka1029

從數組中查找缺少的數字

回答

相關問題