在序列中查找缺失数字的逻辑是什么？

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; 
    } 
}