在序列中查找缺失數字的邏輯是什麼？

Question

我想寫一個簡單的算法來識別整數的ArrayList中第一個丟失的實數。我很難編寫邏輯。觀察我的代碼片段：

// suppose sequence is a valid sorted ArrayList 

int match = 0; 
int first = sequence.get(0); // sets the first value in seq. to var 
int size = sequence.size(); // sets the seq size to var 
for (int i = 0; i < size; i++) 
{ 
    if (i != sequence.get(i) && i > first) 
     match = i; // it is not in the sequence 
} 
System.out.println(match + " is not in the sequence."); 

如果序列4, 5, 8, 9我預計match是6。相反，我得到0。幫幫我？

Answer 1

這是因爲您的if條件要求sequence.get(i)等於i。相反，它應該是first + i，並且需要刪除的條件的第二部分：

if ((first + i) != sequence.get(i)) { 
    match = (first + i); 
    break; 
} 

Demo on ideone.

Answer 2

支票將是類似於sequence.get(i+1) == sequence.get(i) + 1。如果失敗，您將返回sequence.get(i) + 1。

Answer 3

試試這個：

int max = -1; 
for(int i=1; i<sequence.size(); i++) { 
    if(sequence.get(i) > sequence.get(i - 1)) { 
     match = i + 1; 
     break; 
    } 
} 
System.out.println(match + " is not in the sequence."); 

Answer 4

import java.util.Arrays; 
import java.util.List; 
/** 
    <P>{@code java FindMissingNumInSequence}</P> 
**/ 
public class FindMissingNumInSequence { 
    public static final void main(String[] ignored) { 
     List<Integer> ascUnqIntList = Arrays.asList(4, 5, 8, 9); 

     int num = ascUnqIntList.get(0); //Initialize to the first one 
     for(int i : ascUnqIntList) { 
     if(num != i) { 
      System.out.println("First missing number in sequence: " + num); 
      break; 
     } 
     System.out.println(i); 
     num++; 
     } 
    } 
} 

輸出：

[C:\java_code\]java FindMissingNumInSequence 
4 
5 
First missing number in sequence: 6 

Answer 5

這應該可以幫助你獲得你想要的東西，假設數組列表已經排序。

for (int i = 0; i < size - 1; i++) 
{ 
    if (sequence.get(i+1) - sequence.get(i) > 1) { 
     match = sequence.get(i) + 1; // it is not in the sequence 
     break; 
    } 
} 

Answer 6

public class FindMissingNumber { 

public static void main(String args[]){ 
    int[] arr = {5,6,7,0,9}; 

    int start = arr[0]; 
    int length = arr.length; 
    int total = 0; 
    int missing = 0; 
    if(start == 1){ 
     missing = ((length*(length+1))/2) - arrTotal(arr); 
    }else{ 
     total = ((arr[length-1]*(arr[length-1]+1))/2)-(((start-1)*start)/2); 
     missing = total - arrTotal(arr); 
    } 
    System.out.println("Missing Number : "+missing); 
} 

private static int arrTotal(int[] arr){ 
    int total = 0; 
    for(int i = 0; i<arr.length; i++){ 
     total += arr[i]; 
    } 
    return total; 
} 
} 

Answer 7

public class MissingNumber { 

    public static void main(String[] args) { 
     MissingNumber num=new MissingNumber(); 
     int[] numb={2,4,6,10,12,14,}; 
     num.solution(numb); 

    } 
    public int solution(int[] A) { 

     int j=0; 
     int k=0; 
     int missingNum=0; 
     int[] arrayInt=A; 
     int diff=0; 
     for(int i=0;i<arrayInt.length-2;i++) 
     { 
      j=arrayInt[i+1]- arrayInt[i]; 

      k=arrayInt[i+2]-arrayInt[i+1]; 
      if(j==k){ 
       diff= k; 
      } 
      if(j!=k) 
      { 
       if(j!=diff) 
       { 
        missingNum=arrayInt[i]+diff; 
       } 
       else if(k!=diff){ 
        missingNum=arrayInt[i+1]+diff; 
       } 


      } 

     } 
     System.out.println("Missing number"+missingNum); 
     return missingNum; 
    } 
}